- Code:
- #include <bits/stdc++.h>
- #include <tr1/unordered_map>
- #define setIO(s) freopen(s".in","r",stdin)
- #define ll long long
- #define ull unsigned long long
- #define maxn 10000000
- #define mod 1000000007
- #define inv 500000004
- using namespace std;
- using namespace tr1;
- int vis[maxn],prime[maxn],tot;
- ll phi[maxn];
- unordered_map<ll,ull>ansphi;
- void init(){
- phi[1] = 1;
- for(int i=2;i<maxn; ++i) {
- if(!vis[i]) prime[++tot]=i,phi[i] = i-1;
- for(int j=1;j<=tot&&i*prime[j]<maxn;++j) {
- vis[i*prime[j]]=1;
- if(i%prime[j]!=0) phi[i*prime[j]]=phi[i]*(prime[j]-1);
- else {
- phi[i*prime[j]]=phi[i]*(prime[j]);
- break;
- }
- }
- }
- for(int i=1;i<maxn;++i) phi[i]+=phi[i-1],phi[i]%=mod;
- }
- ll solve(ll n){
- if(n < maxn) return phi[n];
- if(ansphi[n]) return ansphi[n];
- ll ans=(ull)(((n%mod)*((n+1)%mod) %mod)*(inv%mod))%mod;
- ll ans2=0;
- for(ll l=2,r;l<=n;l=r+1) {
- r=n/(n/l);
- ans2+=(ll)(r-l+1)*solve(n/l);
- ans2%=mod;
- }
- return ansphi[n]=(ans+mod-ans2)%mod;
- }
- int main(){
- //setIO("input");
- init();
- ll n,ans=0,ans1,tmp;
- scanf("%lld",&n);
- for(ll l=1,r;l<=n;l=r+1){
- r=(n/(n/l));
- ans+=(((n/l)%mod)*((n/l)%mod)%mod*(solve(r)+mod-solve(l-1))%mod)%mod;
- ans%=mod;
- }
- printf("%lld",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2989411.html