POwer oj 2810
2810: Grisaia
Time Limit: 12000 MS Memory Limit: 1048576 KBTotal Submit: 72 Accepted: 13 Page View: 99
Submit Status Discuss
Description
Kazami Kazuki is a talented student.
One day, she met a challengeable problem: calculate the value of
ans=n∑i=1i∑j=1(n mod(i×j))ans=∑i=1n∑j=1i(n mod(i×j))
She worked it out easily. Is it easy for you too?
Input
The first line contains an integer TT representing the number of test cases. In each test case, there is an integer nn in one line. • 1≤T≤51≤T≤5 • 1≤n≤10111≤n≤1011 • It is guaranteed there is at most one test case satisfying that n>109n>109 .
Output
For each test case, output the answer in one line.
2 3 7
2 3 7
10 145
#include<bits/stdc++.h> const int maxn=1e6+10; using namespace std; typedef long long ll; typedef ll lll; bool vis[maxn]; int mu[maxn]; ll sum_muii[maxn]; ll d[maxn]; ll a[maxn]; ll cnt,prim[maxn]; unordered_map<ll,lll> w1; unordered_map<ll,lll> w2; //inline __int128 read(){ // __int128 x=0,f=1; // char ch=getchar(); // while(ch<'0'||ch>'9'){ // if(ch=='-') // f=-1; // ch=getchar(); // } // while(ch>='0'&&ch<='9'){ // x=x*10+ch-'0'; // ch=getchar(); // } // return x*f; //} // inline void print(llx) { if(x<0) { putchar('-'); x=-x; } if(x>9) print(x/10); putchar(x%10+'0');}void init() { mu[1]=1; d[1]=1; for(lli=2;i<maxn;i++) { if(!vis[i]) { prim[++cnt]=i; d[i]=2*i; a[i]=1; mu[i]=-1; } for(intj=1;j<=cnt&&prim[j]*i<maxn;j++) { vis[i*prim[j]]=1; if(i%prim[j]==0) { d[i*prim[j]]=d[i]/(a[i]+1)*(a[i]+2)*prim[j]; a[i*prim[j]]=a[i]+1; break; }else { d[i*prim[j]]=d[i]*d[prim[j]]; a[i*prim[j]]=1; mu[i*prim[j]]=-mu[i]; } } } for(lli=1;i<maxn;i++) { sum_muii[i]=sum_muii[i-1]+mu[i]*i; } for(lli=1;i<maxn;i++) { d[i]=d[i-1]+d[i]; } }lll djsmuii(llx) { if(x<maxn) returnsum_muii[x]; if(w1[x]) returnw1[x]; lll ans=1; for(lll=2,r;l<=x;l=r+1) { r=x/(x/l); ans-=(r+l)*(r-l+1)/2*djsmuii(x/l); } w1[x]=ans; return ans;}lll djsknn(llx) { if(x<maxn) returnd[x]; if(w2[x]) returnw2[x]; lll ans=(lll)x*(x+1)/2; for(lll=2,r;l<=x;l=r+1) { r=x/(x/l); ans-=djsknn(x/l)*(djsmuii(r)-djsmuii(l-1)); } returnans;}lll ask(llx) { llnth=(ll)sqrt(x+0.5); lll tp=(lll)nth*(nth+1)*(2*nth+1)/6; return (djsknn(x)+tp)/2; }lll solve(llx) { lllans=(lll)(1+x)*x*x/2; for(lll=1,r;l<=x;l=r+1) { r=x/(x/l); ans-=(ask(r)-ask(l-1))*(x/l); } returnans;}int main() { init(); int t; cin>>t; while(t--) {// __int128 n; ll n; //n=read(); cin>>n; // printf("%lld\n",solve(n)); print(solve(n)); puts(""); }return 0; }
