部分数论(补
#include<bits/stdc++.h> using namespace std; int main(){ long long n,ans=0; cin >> n; for(long long l=1,r;l<=n;l=r+1){ r = n/(n/l); //计算r,让分块右移 ans += (r-l+1)*(n/l); //求和 cout << l <<""<< r <<": "<< n/r << endl; //打印分块 } cout << ans; //打印和 }
ll ans=0; for(ll l=1,r;l<=n;l=r+1) { if(w/l)r=w/(w/l); else r=n; r=min(r,n); ans+=(r-l+1)*(w/l); }
int prime[N],cnt=0; //prime数组存放所以素数,cnt为素数个数 bool st[N]; //false为素数 int phi[N]; //记录欧拉函数 void get_prime(int n){ phi[1]=1; for(int i=2;i<=n;i++){ if(!st[i]) prime[cnt++]=i,phi[i]=i-1; //把素数i存到prime数组中 for(int j=0;j<cnt&&i*prime[j]<=n;j++){ st[i*prime[j]]=true; //找到的素数的倍数不访问 if(i%prime[j]==0){ phi[i*prime[j]]=phi[i]*prime[j]; break; } phi[i*prime[j]]=phi[i]*phi[prime[j]]; } } }
高精度gcd(Stein算法)
int stein(int a,int b){ if(a<b) a^=b,b^=a,a^=b; //交换,使a为较大数; if(b==0)return a; //当相减为零,即两数相等时,gcd=a; if((!(a&1))&&(!(b&1))) return stein(a>>1,b>>1)<<1; //s1,注意最后的左移,在递归返回过程中将2因子乘上; else if((a&1)&&(!(b&1)))return stein(a,b>>1); //s2; else if((!(a&1))&&(b&1))return stein(a>>1,b); else return stein(a-b,b); //s3; }