Problem C
GCD + LCM
Input: Standard Input

Output: Standard Output

Given the value of N, you will have to find the number of digits in G and L in base googol (). The definition of G and L are given below:

If you are not accustomed with the symbol , then for your kind information we give an example:

Here GCD(i,j) means the greatest common divisor of integer i and integer j, and LCM(i,j) means the Least Common Multiplicand of integer i and integer j.

Input

The input file contains at most 100 lines of inputs. Each line contains an integer N (1<N<1000001). Input is terminated by a line containing a single zero.

Output

For each line of input produce one line of output. This line contains the serial of output followed by two integers DG and DL. Here DG is the number of digits in G when written in base googol and DL is the number of digits in L when written in base googol. Don’t even think of submitting a brute force solution: It will probably take more than 2 years for the largest possible input. Look at the output for sample input for format details.

Sample Input                            Output for Sample Input

Problemsetter: Shahriar Manzoor

Special Thanks: Abdullah-al-Mahmud

參考 [UVA][math] 11424 - GCD - Extreme (I)

背景知識：phi(n) = 小於等於 n 且與 n 互質的個數

題目須要稍微轉換一下，

對於一個數字 n，求 sigma(gcd(n, i)) = ? (i < n)

但這樣還不是很好算, 因此如果我們假設 g = gcd(n, i), 對於一個 g 我們能知道使用了幾次，

已知 gcd(m, i) = 1 的個數 = phi(m), 等價 gcd(m*g, i) = 1*g 的個數 phi(m)

因此只要找到 m = n/g 即可。

先用 sieve 計算 phi(), 然後先枚舉所有可能 g(1~maxn) 對應的 n。

如果先枚舉 n 再枚舉 g(所有因數) 則會太慢。

----
之後再多一個組合的計算，來求 LCM。

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define maxL (1000000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[maxL];
int phi[1000005];
double dp[1000005], sum[1000005];
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1000000;
    for(i = 2; i <= n; i++)
        phi[i] = i;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            phi[i] = phi[i]/i*(i-1);
            for(k = n/i, j = i*k; k >= 2; k--, j -= i) {
                SET(j);
                phi[j] = phi[j]/i*(i-1);
            }
        }
    }
}
int main() {
    sieve();
    int n;
    register int i, j;
    for(i = 1; i <= 1000000; i++) { // gcd(n, ?) = i
        for(j = i+i; j <= 1000000; j += i) {// j = n
            dp[j] += log10(i) * phi[j/i];           
        }
    }
    for(i = 1; i <= 1000000; i++) {
        dp[i] += dp[i-1];
        sum[i] = sum[i-1] + log10(i);
    }
    int cases = 0;
    while(scanf("%d", &n) == 1 && n) {
        double f;
        f = sum[n] * (n-1) - dp[n];
        printf("Case %d: %.0f %.0f\n", ++cases, floor(dp[n]/100.0) + 1, floor(f/100.0) + 1);
    }
    return 0;
}