hdu-6434-欧拉函数 Problem I. Count

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 443 Accepted Submission(s): 232

Problem Description

Multiple query, for each n, you need to get
n i-1
∑ ∑ [gcd(i + j, i - j) = 1]
i=1 j=1

Input

On the first line, there is a positive integer T, which describe the number of queries. Next there are T lines, each line give a positive integer n, as mentioned above.
T<=1e5, n<=2e7

Output

Your output should include T lines, for each line, output the answer for the corre- sponding n.

Sample Input

4 978 438 233 666

Sample Output

194041 38951 11065 89963

Source

2018 Multi-University Training Contest 10

　　 ∑_i=1ⁿ∑^i-1_j=1 [gcd(i + j, i − j) = 1]

　　= [gcd(2i-a,a)=1] (1<=i<=n,1<=a<i)

　　= [gcd(2i,a)=1] 　 (1<=i<=n,1<=a<i)

即对于每个 i, 求有多少个小于它的 a 满足 gcd(i, a) = 1 且a是奇数。

当i是偶数的时候贡献就是 phi(i) ,因为偶数与偶数一定不互质。

当i是奇数的时候贡献是phi(i)/2 ,因为i是奇数，假如x与i互质那么 i-x与i也互质，且x与i-x一个是奇数一个是偶数，所以数量是均等出现的。

 1 #include<bits/stdc++.h> 
 2 using namespace std;  
 3 #define LL long long 
 4 #define mp make_pair
 5 #define pb push_back
 6 #define inf 0x7fffffffff
 7 #define pii pair<int,int>
 8 const int maxn=20000010;
 9 vector<int>prime;
10 bool is[maxn];
11 LL f[maxn];
12 void init(){
13     f[1]=1;
14     is[0]=is[1]=1;
15     for(int i=2;i<=maxn;++i){
16         if(!is[i]) prime.push_back(i),f[i]=i-1;
17         for(int j=0;j<prime.size()&&1LL*i*prime[j]<=maxn;++j){
18             is[i*prime[j]]=1;
19             if(i%prime[j]==0){
20                 f[i*prime[j]]=f[i]*prime[j];
21                 break;
22             }
23             else{
24                 f[i*prime[j]]=f[i]*(prime[j]-1);
25             }
26         }
27     }
28     for(int i=1;i<maxn;++i){
29         if(i&1)f[i]/=2;
30         f[i]+=f[i-1];
31     }
32 }
33 
34 
35 int main()  
36 {
37     init();
38     int t,n;
39     scanf("%d",&t);
40     while(t--){
41         scanf("%d",&n);
42         printf("%lld
",f[n]);
43     }
44     return 0;  
45 }

hdu-6434-欧拉函数 Problem I. Count

相关推荐