题目链接
题意：
求 ( 466<=n<=1e8)
思路：
找规律得以下公式。。。然后首尾的不计的phi单独处理即可
代码：
#include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; const long long mod = 1e9+7; namespace prime_table{ const int MAX_N = 233; int all=0; int pr[MAX_N/10+100]; int phi[MAX_N+10]; bool isp[MAX_N+10]; inline int get_phi(int n){ int m = sqrt(n+0.5); int p = n; for(int i=2;i<=m&&n>1 ;i++) { if(n%i==0){ p = p / i * (i-1); do{n/=i;}while(n%i==0); } }if(n>1)p = p / n * (n-1); return p ; } inline void init(){ memset(isp,0,sizeof(isp)); for(int i=2;i<=MAX_N;i++){ if(!isp[i]){ pr[all++] = i; phi[i] = i - 1; } for(int j=0;j<all;j++){ long long t = pr[j] * i; if(t>MAX_N){ break; } isp[t] = true; if(i%pr[j]==0){ phi[t] = phi[i] * pr[j]; break; }else { phi[t] = phi[i] * ( pr[j]-1 ); } } } } } using namespace prime_table; int main() { init(); int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); long long ans = 1LL * n * (n-1) / 2 ; for(int i=1;i<233;i++){ ans -= 1LL * phi[i] * (n/i); }for(int i=n-232;i<=n;i++){ ans -= 1LL * get_phi(i) * (n/i) ; }printf("%lld\n",ans%mod); }return 0; }
