• 2810: Grisaia

    Time Limit: 12000 MS Memory Limit: 1048576 KB
    Total Submit: 72 Accepted: 13 Page View: 99
    Submit Status Discuss
    ×

    Submit Problem 2810:Grisaia

    ×Sorry, youd don't have permission to submit solution.
    SubmitCancel

    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 

    #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; }