ACM ICPC Dhaka Regional 2008: Puzzles of Triangles

Tags: Euler's Totient Function, Divisor Sum Theorem, Dirichlet Convolution, Sieve of Eratosthenes, Similar Triangles

Problem Statement:

Solution: Let’s assume, $BE = X$. Connect $A$ with $E$. Draw a perpendicular line to $AE$ that intersects $DC$ at $F$. It’s evident that all 4 triangles are right angled. The only doubt that remains is whether $F$ is a lattice point or not. We choose $BE$ to be an integer. Since, $\triangle ABE$ and $\triangle ECF$ are similar. We get,

$CF = k = \frac{(N-X)X}{N}$

We want $k$ to be an integer. So the right hand side must be an integer. Let’s take $N = ng$ and $X = xg$ where $g = \gcd(N,X)$. So, definitely $\gcd(x,n) = 1$. So,

$CF = k = \frac{(n-x)xg}{n}$

Since $\gcd(x,n) = \gcd(n-x,n) = 1$, so $n$ divides $g$. Thus, $g = f \times n$ for some positive integer $f$.
So, $N = f n^{2}$ and $X = f n x$. So, for every square divisor $n^2$ of $N$, we will get $f$ and also, for every $x$ that is less than $n$ and co-prime to $n$, we can make a tuple $(f, n, x)$ and thus an $X$.
Let $N$ have the following prime factorization,

$N = p_{1}^{a_{1}}p_{2}^{a_{2}} \cdots p_{k}^{a_{k}}$

Since, $N = f n^{2}$, so $n \leq \sqrt{N}$. What we want is actually, if,

$M = p_{1}^{\lfloor \frac{a_{1}}{2} \rfloor }p_{2}^{\lfloor \frac{a_{2}}{2} \rfloor } \cdots p_{k}^{\lfloor \frac{a_{k}}{2} \rfloor }$

Then our answer is, ($\sum_{d|M} \varphi(d)) - 1$ because, if $n = 1$, there is no non-zero $x$ that is less than $n$.
But, We can easily prove that, $\sum_{d|M} \varphi(d) = M$.
Proof:
Since $\varphi(n)$ and $g(n) = 1$ are multiplicative functions, let’s define the following Dirichlet Convolution

$f(n) = (\varphi * g) (n) = \sum_{d|n} \varphi(d) g(\frac{n}{d}) = \sum_{d|n} \varphi(d)$

which is also a multiplicative function.
It can be easily seen that for a prime power $p^{a}$,

$f(p^{a}) = \varphi(1) + \varphi(p^{1}) + \varphi(p^{2})+ \cdots + \varphi(p^{a-1}) + \varphi(p^{a})$ $f(p^{a}) = p^{0} + p^{1} - p^{0} + p^{2} - p^{1}+ \cdots + p^{a-1} - p^{a-2} + p^{a} - p^{a-1} = p^{a}$

So,

$f(M) = f(p_{1}^{x_{1}}p_{2}^{x_{2}} \cdots p_{k}^{x_{k}}) = f(p_{1}^{x_{1}}) f(p_{2}^{x_{2}}) \cdots f(p_{k}^{x_{k}}) = p_{1}^{x_{1}}p_{2}^{x_{2}} \cdots p_{k}^{x_{k}} = M$.

And also, notice that, we could start the construction from any of the 4 corners and the point $E$ could be chosen from 2 sides for each. So, there are total 8 possible configuration each having $M-1$ possible lattice points for $F$. So, the answer is $8(M-1)$.
Implementation:


#include <bits/stdc++.h>
#define MAX 10000000

using namespace std;

bool status[MAX+10];
vector  v;

void sieve(){
    int limit = sqrt(MAX);
    for(int i = 3; i <= limit; i+=2){
        if(status[i]==false){
            for(int j = i *i; j <= MAX; j+=i+i){
                status[j]=true;
            }
        }
    }
    v.push_back(2);
    for(int i = 3; i <= MAX; i++){
        if(status[i]==false){
            v.push_back(i);
        }
    }
}

long long factorize(long long N){
    long long ret = 1LL;
    for(int i = 0; i < v.size() and v[i]*v[i] <= N; i++){
        int p = v[i];
        if(N%p==0){
            int cnt = 0;
            while(N%p==0){
                cnt++;
                N/=p;
            }
            cnt = cnt / 2;
            while(cnt){
                ret = ret * p;
                cnt--;
            }
        }
    }
    return ret;
}

int main(){
    sieve();
    long long N;
    int t = 0;
    while(true){
        scanf("%lld",&N);
        if(N==0) break;
        t++;
        long long x = factorize(N)-1;
        if(x) printf("Case %d: %lld\n",t,8LL*x);
        else printf("Case %d: Impossible\n",t);
    }
    return 0;
}
</pre>