Problem I. Count

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

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

令a=i-j,所以i+j=2*i-a，那么原式可以化简为：

a一定是奇数。

1 欧拉函数的几个性质：f(n) :欧拉函数值
2 1.若a为质数,phi[a]=a-1;
3 2.若a为质数,b mod a=0,phi[a*b]=phi[b]*a
4 3.若a,b互质,phi[a*b]=phi[a]*phi[b](当a为质数时,if b mod a!=0 ,phi[a*b]=phi[a]*phi[b])
5 4.gcd(kx,ky)=gcd(x,y)==1
6 5.gcd(kx-y,y)=gcd(kx,y)=gcd(x,y)==1
7 6.若N为奇数，那么f(2*n)=2*f(n)   
8 7.若n是质数p的k次幂，f(n)=p^k-p^(k-1)=(p-1)*p^(k-1)
9 因为除了p的倍数外，其他数都跟n互质。:1~n 每隔p个出现一个p的倍数

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<vector>
 7 #define N 20000009
 8 using namespace std;
 9 #define ll long long 
10 int pre[N],phi[N];
11 ll sum[N];
12 bool vis[N];
13 int t,n;
14 //欧拉函数 ：phi[i] j:(1~i)里有phi[i]个数令gcd(i,j)=1
15 void init()
16 {
17     pre[1]=1;//先赋值为1
18     int i,j;
19     int pree=0;
20     for(i=2;i<=N;i++)
21     {
22         if(!vis[i]){
23             pre[++pree]=i;
24             phi[i]=i-1;
25         }
26         for(j=1;j<=pree&&i*pre[j]<=N;j++){
27             vis[i*pre[j]]=1;
28             if(i%pre[j]==0){
29                 phi[i*pre[j]]=phi[i]*pre[j];
30                 break;
31             }
32             else{
33                 phi[i*pre[j]]=phi[i]*phi[pre[j]];
34             }
35         }
36     }
37     for(int i=1;i<=N;i++){
38         if(i&1) phi[i]>>=1;          
39         sum[i]=sum[i-1]+phi[i];//求个前缀和即可
40         //if(i&1) phi[i]>>=1;
41         //因为a一定是奇数，那么偶数不变，因为偶数与偶数的gcd一定！=1
42         //奇数减半 如 7 ： 1 2 3 4 5 6  而只有1 3 5 有效
43     }
44 }
45 int main()
46 {  
47     init();
48     scanf("%d",&t);
49     while(t--){
50         scanf("%d",&n);
51         printf("%lld
",sum[n]);
52     }
53     return 0;
54 }

UVA 11426

Given the value of N, you will have to find the value of G. The definition of G is given below:
Here GCD(i, j) means the greatest common divisor of integer i and integer j.
For those who have trouble understanding summation notation, the meaning of G is given in the
following code:
G=0;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
G+=gcd(i,j);
}
/*Here gcd() is a function that finds
the greatest common divisor of the two
input numbers*/
Input
The input file contains at most 100 lines of inputs. Each line contains an integer N (1 < N < 4000001).
The meaning of N is given in the problem statement. 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 value of G for the corresponding
N. The value of G will fit in a 64-bit signed integer.

Sample Input

100

200000

Sample Output

13015
143295493160

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<vector>
 7 #define N 4000009
 8 using namespace std;
 9 #define ll long long 
10 #define mem(a,b)  memset(a,b,sizeof(a))
11 #define inf 0x3f3f3f3f
12 int pre[N],phi[N];
13 int n;
14 bool vis[N];
15 ll sum[N],f[N];
16 void init()
17 {
18     phi[1]=1;
19     int i,j,pree=0;
20     for(i=2;i<N;i++)
21     {
22         if(!vis[i]){
23             pre[++pree]=i;
24             phi[i]=i-1;
25         }
26         for(j=1;j<=pree&&i*pre[j]<N;j++)
27         {
28             vis[i*pre[j]]=1;
29             if(i%pre[j]==0){
30                 phi[i*pre[j]]=phi[i]*pre[j];
31                 break;
32             }
33             else{
34                 phi[i*pre[j]]=phi[i]*phi[pre[j]];
35             }
36         }
37     }
38     for(i=1;i<N;i++){
39         for(j=i*2;j<N;j+=i){//i*2开始
40             f[j]+=i*phi[j/i];//如果直接对于每个n求出约数来更新f(n)是超时的
41         }
42     }
43     for(i=1;i<N;i++){
44         sum[i]=sum[i-1]+f[i];
45     }
46 }
47 int main()
48 {   
49     init();
50     while(~scanf("%d",&n)&&n){
51         printf("%lld
",sum[n]);
52     }
53 }

题面描述
最近，华东交通大学ACM训练基地的老阿姨被一个数学问题困扰了很久，她希望你能够帮她解决这个问题。
这个数学问题是这样的，给你一个N,要求你计算

gcd(a,b)表示a和b的最大公约数

输入描述:

多组输入，每行一个整数n(1<=n<=10^14)。

输出描述:

每行一个整数，表示答案。由于答案会很大你要对1000000007取模。

示例1

输入

复制

4
10

输出

复制

6
35

说明

样例一，2+4=6。
样例二，2+4+5+6+8+10=35。

https://ac.nowcoder.com/acm/contest/221/I

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <utility>
#include <queue>
using namespace std;
#define ph push_back
const int inf =0x3f3f3f3f;
#define ll long long
using namespace std;
const int N = 1e5+9;
const ll mod = 1e9+7;
void  egcd(ll a,ll b,ll &x,ll &y,ll &d)
{
    if(!b){
        d=a,x=1,y=0;
    }
    else{
        egcd(b,a%b,y,x,d);
        y-=x*(a/b);
    }
}
ll inv(ll t,ll p)
{
    ll x,y,d;
    egcd(t,p,x,y,d);
    return d==1?(x%p+p)%p:-1;
}
ll phi(ll a){//求欧拉值
    ll ans = a;
    for(ll i = 2; i*i <= a; i++){
        if(a % i == 0){
            ans = ans / i * (i-1);
            while(a % i == 0) a /= i;
        }
    }
    if(a > 1) ans = ans / a * (a-1);
    return ans%mod;
}
ll n;
int  main()
{
    while(~scanf("%lld",&n)){
        if(n==1) 
        {
            printf("0
");//不然会输出500000004
            continue;
        }
        ll t1=((n%mod)*((n+1)%mod)%mod*inv(2,mod))%mod;//1~n的和
        ll t2=(n%mod)*phi(n)%mod*inv(2,mod)%mod;//一定是成对的
        /*
        14
        1 13
        3 11
        ......
        */
        ll t=(((t1-t2)%mod+mod)%mod);
        printf("%lld
",t);
    }
    return 0;
}