P1390 公约数的和

题目描述

有一天，TIBBAR和LXL比赛谁先算出1~N这N个数中每任意两个不同的数的最大公约数的和。LXL还在敲一个复杂而冗长的程序，争取能在100s内出解。而TIBBAR则直接想1s秒过而获得完胜，请你帮他完成这个任务。

输入输出格式

输入格式：

共一行，一个正整数N。

输出格式：

共一行，一个数，为1~N这N个数中每任意两个不同的数的最大公约数的和。

输入输出样例

输入样例#1：

10

输出样例#1：

67

说明

对于40%的数据，2≤N≤2000.

对于100%的数据，2≤N≤2000000.

 

 

这个题怪好

不妨设f(n) = (1,n) + (2,n) + (3,n) + (4,n) + ... + (n-2,n) + (n-1,n)

则答案为f(2) + f(3) + f(4) + ... + f(n - 1) + f(n)

对于任意数i，若(i, n) = k,  则(i/k, n/k) = 1，不难得到

f(n) = Σ(i | n)phi(n/i) * i

对于每个i，枚举其倍数n即可

 

#include 
      
       #include 
       
        #include 
        
         #include 
         
           #include 
          
           #include 
           
            #include 
            
             inline void read(long long &x){x = 0;char ch = getchar();char c = ch;while(ch > '9' || ch < '0')c = ch, ch = getchar();while(ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();}inline int max(int a, int b){ return a > b ? a : b;}inline int min(int a, int b){ return a < b ? a : b;}inline void swap(int &a, int &b){ int tmp = a;a = b;b = tmp;}const int INF = 0x3f3f3f3f;const int MAXN = 2000000 + 10;long long n;long long ans;long long prime[MAXN],phi[MAXN],cnt;bool bp[MAXN];inline void makephi(){ phi[1] = 1; for(register long long i = 2;i <= n;++ i) { if(!bp[i]) prime[++cnt] = i, phi[i] = i - 1; for(register long long j = 1;j <= cnt;++ j) { if(i * prime[j] > n)break; bp[i* prime[j]] = 1; if(i % prime[j] == 0) { phi[i * prime[j]] = phi[i] * prime[j]; break; } else phi[i * prime[j]] = phi[i] * (prime[j] - 1); } }}long long f[MAXN];int main(){ read(n); makephi(); for(register int i = 1;i <= n;i ++) { for(register int j = i * 2;j <= n;j += i) { f[j] += phi[j / i] * i; } } for(register int i = 2;i <= n;++ i) ans += f[i]; printf("%lld", ans); return 0;}