https://www.luogu.org/problemnew/show/P2158
好像以前有个妹子收割铲也是欧拉函数.
因为格点直线上的点, dx 与 dy 的 gcd 相同, 画个图就觉得是欧拉函数. 但是要注意对称轴还有左下角那个破点!
- #include<bits/stdc++.h>
- using namespace std;
- #define ll long long
- const int MAXN=40000+5;
- int phi[MAXN];
- int pri[MAXN],pritop;
- bool notpri[MAXN];
- //pritop 从 1 开始计数
- void sieve2(int n) {
- notpri[1]=phi[1]=1;
- for(int i=2; i<=n; i++) {
- if(!notpri[i])
- pri[++pritop]=i,phi[i]=i-1;
- for(int j=1; j<=pritop&&i*pri[j]<=n; j++) {
- notpri[i*pri[j]]=1;
- // 略有不同
- if(i%pri[j])
- phi[i*pri[j]]=phi[i]*phi[pri[j]];
- else {
- phi[i*pri[j]]=phi[i]*pri[j];
- break;
- }
- }
- }
- }
- int main(){
- sieve2(40000);
- int n;
- cin>>n;
- if(n==1)
- cout<<"0"<<endl;
- else{
- ll sumphi=0;
- for(int i=1;i<n;i++){
- sumphi+=phi[i];
- }
- sumphi*=2;
- sumphi+=1;
- cout<<sumphi<<endl;
- }
- }
来源: http://www.bubuko.com/infodetail-3020160.html