NBUT1613 GCD（容斥)

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 __int64 num[400010];
 6 int main()
 7 {
 8     int n;
 9     
10     __int64 ans = 0;
11     while (~scanf("%d",&n))
12     {
13         ans = 0;
14         memset(num,0,sizeof(num));
15         if (n == 0)
16         {
17             break;
18         }
19         for (int i = n ; i >= 1 ; --i )
20         {
21             __int64 temp = n / i;                //计算从i~n中能被i整除的数字有几个
22             if(temp <= 1)                        //如果小于等于1  就说明没有
23             {
24                 num[i] = 0;
25             }
26             else 
27             {
28                 num[i] = temp * (temp -1 ) / 2;        //这个是i~n,i~n-1，i~n-2，，，这些的和
29             }
30 
31             for (int j = 2 * i ; j <= n ; j += i)        //如果能被i 整除，并且又能被i 的倍数整除，那么 公约数不会是i  所以需要减去能被i倍数整除的个数
32             {
33                 num[i] -= num[j];
34             }
35             ans += num[i] * i;        //i为最大公约数的个数乘于i ，，就是i 这个数总共的和
36         }
37         printf("%I64d\n",ans);            //最后输出答案
38     }
39     return 0;
40 }