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
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
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
978
438
233
666
Sample Output
194041
38951
11065
89963
38951
11065
89963
Source
∑i=1n∑i-1j=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一个是奇数一个是偶数，所以数量是均等出现的。
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define mp make_pair
#define pb push_back
#define inf 0x7fffffffff
#define pii pair<int,int>
const int maxn=;
vector<int>prime;
bool is[maxn];
LL f[maxn];
void init(){
f[]=;
is[]=is[]=;
for(int i=;i<=maxn;++i){
if(!is[i]) prime.push_back(i),f[i]=i-;
for(int j=;j<prime.size()&&1LL*i*prime[j]<=maxn;++j){
is[i*prime[j]]=;
if(i%prime[j]==){
f[i*prime[j]]=f[i]*prime[j];
break;
}
else{
f[i*prime[j]]=f[i]*(prime[j]-);
}
}
}
for(int i=;i<maxn;++i){
if(i&)f[i]/=;
f[i]+=f[i-];
}
} int main()
{
init();
int t,n;
scanf("%d",&t);
while(t--){
scanf("%d",&n);
printf("%lld\n",f[n]);
}
return ;
}