欧拉函数

例题一：洛谷P2568 GCD

题目描述

给定正整数 nn，求 1\le x,y\le n1≤x,y≤n 且 \gcd(x,y)gcd(x,y) 为素数的数对 (x,y)(x,y) 有多少对。

输入格式

只有一行一个整数，代表nn。

输出格式

一行一个整数表示答案。

输入输出样例

输入

4

输出

4

#include <bits/stdc++.h> using namespace std; long long n,k[10000005]={},j,ans,f[10000005]; bool r[10000005]; int main(){ f[1]=1; scanf("%lld",&n); for(long long i=2;i<=n;i++){ if(!r[i]){ k[++j]=i; r[i]=1; f[i]=i-1; } for(long long l=1;l<=j&&i*k[l]<=n;l++) { r[i*k[l]]=1; if(i%k[l]==0){ f[i*k[l]]=f[i]*k[l]; break; } else f[i*k[l]]=f[i]*(k[l]-1); } } for(long long i=1;i<=n;i++){ f[i]+=f[i-1]; } for(long long i=j;i>0;i--){ ans+=f[n/k[i]]*2; } printf("%lld",ans-j); return 0; }

例题二：公约数之和

题目描述

给定正整数n(1 < n < 2^31)，计算∑gcd(i, n) 1<=i <=n。

输入格式

多组数据，每组数据的格式为：

第1行：1个整数n

输出格式

对每个数据，在1行：1个整数，表示如题所求的结果

样例

样例输入

6

样例输出

15

#include<bits/stdc++.h> using namespace std; long long n,r[100005],cnt,o,k[100005],k1[100005],a[100005],ans,j=1; void f(long long x,long long y){ if(x==j){ r[++cnt]=y; return; } for(long long i=0;i<=k[x];i++){ f(x+1,y*pow(k1[x],i)); } } long long u=0; long long g(long long x){ long long o=1,ans1=x,p=x,f=0; for(long long i=2;i*i<=p;i++){ while(p%i==0){ p/=i; if(f==0)ans1=ans1/i*(i-1); f=1; } f=0; } if(p!=1){ ans1=ans1/p*(p-1); } return ans1; } int main(){ while(scanf("%lld",&n)!=EOF){ ans=0; j=1; cnt=0; o=n; memset(k,0,sizeof(k)); for(long long i=2;i*i<=o;i++){ while(o%i==0){ k[j]++; k1[j]=i; o/=i; } if(k[j]!=0){ j++; } } if(o!=1){ k[j]++; k1[j]=o; j++; } f(1,1); for(long long i=1;i<=cnt;i++){ ans+=g(n/r[i])*r[i]; } printf("%lld\n",ans); } return 0; }

例题三：UVA11424 GCD - Extreme (I)

大概意思是求

for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ ans+=gcd(i,j); } }

代码

#include<bits/stdc++.h> using namespace std; long long n1,r[200005],cnt,a[200005],ans,j=1,ans3[200005]; long long u=0,phi[200005]={},p[200005]={}; bitset<2000005>m; void g(long long n){ phi[1]=1; for(long long i=2;i<=n;i++){ if (!m[i]){ p[++u]=i; phi[i]=i-1; } for (long long j=1;j<=u&&p[j]*i<=n;j++){ m[p[j]*i]=1; if(i%p[j]==0){ phi[p[j]*i]=phi[i]*p[j]; break; } else phi[p[j]*i]=phi[i]*(p[j]-1); } } } long long h(long long n){ ans=0; cnt=0; for(long long i=1;i*i<=n;i++){ if(n%i==0){ r[++cnt]=i; if(i!=n/i)r[++cnt]=n/i; } } for(long long i=1;i<=cnt;i++){ ans+=phi[n/r[i]]*r[i]; } return ans; } int main(){ long long ans2=0; g(200000); ans2=0; for(int i=1;i<=200000;i++){ ans2+=h(i)-i; ans3[i]=ans2; } while(scanf("%lld",&n1)&&n1){ printf("%lld\n",ans3[n1]); } return 0; }

例题四：[NOI2010]能量采集

题目描述

栋栋有一块长方形的地，他在地上种了一种能量植物，这种植物可以采集太阳光的能量。在这些植物采集能量后，栋栋再使用一个能量汇集机器把这些植物采集到的能量汇集到一起。

栋栋的植物种得非常整齐，一共有 nn 列，每列有 mm 棵，植物的横竖间距都一样，因此对于每一棵植物，栋栋可以用一个坐标 (x, y)(x,y) 来表示，其中 xx 的范围是 11 至 nn，yy 的范围是 11 至 mm，表示是在第 xx 列的第 yy 棵。

由于能量汇集机器较大，不便移动，栋栋将它放在了一个角上，坐标正好是 (0, 0)(0,0)。

能量汇集机器在汇集的过程中有一定的能量损失。如果一棵植物与能量汇集机器连接而成的线段上有 kk 棵植物，则能量的损失为 2k + 12k+1。例如，当能量汇集机器收集坐标为 (2, 4)(2,4) 的植物时，由于连接线段上存在一棵植物 (1, 2)(1,2)，会产生 33 的能量损失。注意，如果一棵植物与能量汇集机器连接的线段上没有植物，则能量损失为 11。现在要计算总的能量损失。

下面给出了一个能量采集的例子，其中 n = 5n=5，m = 4m=4，一共有 2020 棵植物，在每棵植物上标明了能量汇集机器收集它的能量时产生的能量损失。

在这个例子中，总共产生了 3636 的能量损失。

输入格式

一行两个整数 n,mn,m。

输出格式

仅包含一个整数，表示总共产生的能量损失。

输入输出样例

输入1

5 4

输出1

36

输入2

3 4

输出2

20 再用之前的算法就超时了 下面是另一种算法(这种算法也可以A上面一些题)

#include<bits/stdc++.h> using namespace std; long long n,m; long long sum[100005],ans; int main(){ scanf("%lld%lld",&n,&m); if(n>m)swap(n,m); for(long long i=n;i>=1;i--){ sum[i]=(n/i)*(m/i); for(long long j=i*2;j<=n;j+=i){ sum[i]-=sum[j]; } ans+=(i*2-1)*sum[i]; } printf("%lld",ans); return 0; }