QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#750569#9612. 月亮的背面是粉红色的Nesraychan84 1892ms323340kbC++144.6kb2024-11-15 15:01:162024-11-15 15:01:17

Judging History

你现在查看的是最新测评结果

  • [2024-11-15 15:01:17]
  • 评测
  • 测评结果：84
  • 用时：1892ms
  • 内存：323340kb
查看
  • [2024-11-15 15:01:16]
  • 提交

answer

#include<bits/stdc++.h>
#define IL inline
#define reg register
#define N 32000005
#define M 2000200
#define int long long
#define mod 1000000007
IL int read()
{
    reg int x=0,f=0; reg char ch=getchar();
    while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}

IL int Add(reg int x,reg int y){return x+y<mod?x+y:x+y-mod;}
IL int Sub(reg int x,reg int y){return x<y?x-y+mod:x-y;}
IL void Pls(reg int &x,reg int y){x=Add(x,y);}
IL void Dec(reg int &x,reg int y){x=Sub(x,y);}
IL int Mul(reg int x,reg int y){reg long long r=1ll*x*y; return r<mod?r:r%mod;}
IL int power(reg int x,reg int p){reg int r=1; for(;p;p>>=1,x=Mul(x,x))if(p&1)r=Mul(r,x); return r;}

const int inv2=mod+1>>1,B=3.2e7;
int n,m,pri[M],tot;
std::bitset<N>isp;

IL void sieve(reg int n)
{
    tot=0; 
    for(reg int i=2,j,v;i<=n;++i)
    {
        if(!isp[i])pri[++tot]=i;
        for(j=1;j<=tot&&(v=i*pri[j])<=n;++j)
        {
            isp[v]=1;
            if(i%pri[j]==0)break;
        }
    }
}

int h[M][3],ans0,ans1;

IL int A(reg int n)
{
    n%=mod;
    return Mul(Mul(n,n+1),inv2);
}

int f0[N],f1[N],g0[N],g1[N];

IL void upd(reg int k0,reg int k1,reg int m)
{
    if(m<=B)Pls(f0[m],k0),Pls(f1[m],k1);
    else Pls(g0[n/m],k0),Pls(g1[n/m],k1);
    // reg int s0=0,s1=0,i1=1,i2=2,i3=3,i4=4,i5=5,i6=6,i7=7,i8=8;
    // while(i8*i8<=n)
    // {
    //     s0+=n/i1,Pls(s1,Mul(i1,A(n/i1))),i1+=8;
    //     s0+=n/i2,Pls(s1,Mul(i2,A(n/i2))),i2+=8;
    //     s0+=n/i3,Pls(s1,Mul(i3,A(n/i3))),i3+=8;
    //     s0+=n/i4,Pls(s1,Mul(i4,A(n/i4))),i4+=8;
    //     s0+=n/i5,Pls(s1,Mul(i5,A(n/i5))),i5+=8;
    //     s0+=n/i6,Pls(s1,Mul(i6,A(n/i6))),i6+=8;
    //     s0+=n/i7,Pls(s1,Mul(i7,A(n/i7))),i7+=8;
    //     s0+=n/i8,Pls(s1,Mul(i8,A(n/i8))),i8+=8;
    // }
    // while(i1*i1<=n)s0+=n/i1,Pls(s1,Mul(i1,A(n/i1))),++i1;
    // s0=(s0+s0-(i1-1)*(i1-1))%mod;
    // s1=Sub(Add(s1,s1),power(A(i1-1),2));
    // Pls(ans0,Mul(s0,k0)),Pls(ans1,Mul(s1,k1));
}

void dfs(reg int i,reg int x,reg int f0,reg int f1)
{
    if(i>tot||pri[i]*pri[i]>x)
    {
        upd(f0,f1,x);
        return;
    }
    dfs(i+1,x,f0,f1),x/=pri[i];
    for(reg int j=2;j<=2;++j)
        x/=pri[i],dfs(i+1,x,mod-f0,Mul(f1,h[i][j]));
}

main()
{
    n=read(),m=read();
    reg int lim=1;
    while(lim*lim<=n)++lim;
    sieve(lim-1);
    for(reg int i=1,x,j,k,up;i<=tot;++i)
    {
        static int f[60],g[60];
        f[0]=g[0]=1,up=0;
        for(j=x=1;x<=n/pri[i];++j)
            x*=pri[i],up=j,f[j]=x*2%mod,g[j]=x%mod;
        for(j=1;j<=up;++j)for(k=0;k<j;++k)
            Dec(f[j],Mul(f[k],g[j-k]));
        for(j=1;j<=up;++j)for(k=0;k<j;++k)
            Dec(f[j],Mul(f[k],g[j-k]));
        for(j=0;j<=2;++j)h[i][j]=f[j]; 
    }
    fprintf(stderr,"%.3lf\n",1.0*clock()/CLOCKS_PER_SEC);
    dfs(1,n,1,1);
    for(reg int x=1,m;x<=B;++x)if(f0[x]||f1[x])
    {
        m=x;
        reg int s0=0,s1=0,i1=1,i2=2,i3=3,i4=4,i5=5,i6=6,i7=7,i8=8;
        while(i8*i8<=m)
        {
            s0+=m/i1,Pls(s1,Mul(i1,A(m/i1))),i1+=8;
            s0+=m/i2,Pls(s1,Mul(i2,A(m/i2))),i2+=8;
            s0+=m/i3,Pls(s1,Mul(i3,A(m/i3))),i3+=8;
            s0+=m/i4,Pls(s1,Mul(i4,A(m/i4))),i4+=8;
            s0+=m/i5,Pls(s1,Mul(i5,A(m/i5))),i5+=8;
            s0+=m/i6,Pls(s1,Mul(i6,A(m/i6))),i6+=8;
            s0+=m/i7,Pls(s1,Mul(i7,A(m/i7))),i7+=8;
            s0+=m/i8,Pls(s1,Mul(i8,A(m/i8))),i8+=8;
        }
        while(i1*i1<=m)s0+=m/i1,Pls(s1,Mul(i1,A(m/i1))),++i1;
        s0=(s0+s0-(i1-1)*(i1-1))%mod;
        s1=Sub(Add(s1,s1),power(A(i1-1),2));
        Pls(ans0,Mul(s0,f0[x])),Pls(ans1,Mul(s1,f1[x]));
    }
    for(reg int x=1,m;x<=B;++x)if(g0[x]||g1[x])
    {
        m=n/x;
        reg int s0=0,s1=0,i1=1,i2=2,i3=3,i4=4,i5=5,i6=6,i7=7,i8=8;
        while(i8*i8<=m)
        {
            s0+=m/i1,Pls(s1,Mul(i1,A(m/i1))),i1+=8;
            s0+=m/i2,Pls(s1,Mul(i2,A(m/i2))),i2+=8;
            s0+=m/i3,Pls(s1,Mul(i3,A(m/i3))),i3+=8;
            s0+=m/i4,Pls(s1,Mul(i4,A(m/i4))),i4+=8;
            s0+=m/i5,Pls(s1,Mul(i5,A(m/i5))),i5+=8;
            s0+=m/i6,Pls(s1,Mul(i6,A(m/i6))),i6+=8;
            s0+=m/i7,Pls(s1,Mul(i7,A(m/i7))),i7+=8;
            s0+=m/i8,Pls(s1,Mul(i8,A(m/i8))),i8+=8;
        }
        while(i1*i1<=m)s0+=m/i1,Pls(s1,Mul(i1,A(m/i1))),++i1;
        s0=(s0+s0-(i1-1)*(i1-1))%mod;
        s1=Sub(Add(s1,s1),power(A(i1-1),2));
        Pls(ans0,Mul(s0,g0[x])),Pls(ans1,Mul(s1,g1[x]));
    }
    if(!m)printf("%lld\n",power(ans0,2));
    else printf("%lld %lld\n",power(ans0,2),power(ans1,2));
    fprintf(stderr,"%.3lf\n",1.0*clock()/CLOCKS_PER_SEC);
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 3
Accepted

Test #1:

score: 3
Accepted
time: 40ms
memory: 8088kb

input:

1726 1

output:

84290761 74619067

result:

ok 2 number(s): "84290761 74619067"

Test #2:

score: 3
Accepted
time: 39ms
memory: 8112kb

input:

3608 1

output:

433014481 672891299

result:

ok 2 number(s): "433014481 672891299"

Test #3:

score: 3
Accepted
time: 39ms
memory: 8136kb

input:

2921 1

output:

271096225 547734266

result:

ok 2 number(s): "271096225 547734266"

Subtask #2:

score: 3
Accepted

Test #4:

score: 3
Accepted
time: 40ms
memory: 8396kb

input:

6116899 1

output:

219318963 301450440

result:

ok 2 number(s): "219318963 301450440"

Test #5:

score: 3
Accepted
time: 40ms
memory: 8348kb

input:

6260707 1

output:

148720176 263856753

result:

ok 2 number(s): "148720176 263856753"

Test #6:

score: 3
Accepted
time: 36ms
memory: 8352kb

input:

6763677 1

output:

944542490 136397156

result:

ok 2 number(s): "944542490 136397156"

Subtask #3:

score: 8
Accepted

Test #7:

score: 8
Accepted
time: 40ms
memory: 10952kb

input:

6469467712 0

output:

147393348

result:

ok 1 number(s): "147393348"

Test #8:

score: 8
Accepted
time: 37ms
memory: 13228kb

input:

8967004453 0

output:

229436583

result:

ok 1 number(s): "229436583"

Test #9:

score: 8
Accepted
time: 36ms
memory: 10868kb

input:

6636594384 0

output:

995965072

result:

ok 1 number(s): "995965072"

Subtask #4:

score: 8
Accepted

Test #10:

score: 8
Accepted
time: 41ms
memory: 11216kb

input:

8292948816 1

output:

566765721 287485757

result:

ok 2 number(s): "566765721 287485757"

Test #11:

score: 8
Accepted
time: 37ms
memory: 11228kb

input:

8592748771 1

output:

649470692 164561252

result:

ok 2 number(s): "649470692 164561252"

Test #12:

score: 8
Accepted
time: 41ms
memory: 11440kb

input:

9827380808 1

output:

291159931 188690805

result:

ok 2 number(s): "291159931 188690805"

Subtask #5:

score: 8
Accepted

Test #13:

score: 8
Accepted
time: 90ms
memory: 27176kb

input:

900472451132 1

output:

247050500 963765719

result:

ok 2 number(s): "247050500 963765719"

Test #14:

score: 8
Accepted
time: 77ms
memory: 28892kb

input:

850862494659 1

output:

200210720 915108650

result:

ok 2 number(s): "200210720 915108650"

Test #15:

score: 8
Accepted
time: 95ms
memory: 26872kb

input:

851346512859 1

output:

895785763 504512885

result:

ok 2 number(s): "895785763 504512885"

Subtask #6:

score: 10
Accepted

Test #16:

score: 10
Accepted
time: 195ms
memory: 56540kb

input:

9864907300784 1

output:

359943536 720268421

result:

ok 2 number(s): "359943536 720268421"

Test #17:

score: 10
Accepted
time: 188ms
memory: 55520kb

input:

8181674676063 1

output:

839993102 994056029

result:

ok 2 number(s): "839993102 994056029"

Test #18:

score: 10
Accepted
time: 193ms
memory: 58764kb

input:

9893510217522 1

output:

157499971 930653488

result:

ok 2 number(s): "157499971 930653488"

Subtask #7:

score: 13
Accepted

Test #19:

score: 13
Accepted
time: 575ms
memory: 134408kb

input:

96735749745529 0

output:

223354886

result:

ok 1 number(s): "223354886"

Test #20:

score: 13
Accepted
time: 576ms
memory: 128212kb

input:

95243570720799 0

output:

555372474

result:

ok 1 number(s): "555372474"

Test #21:

score: 13
Accepted
time: 588ms
memory: 129380kb

input:

97668723090105 0

output:

84562124

result:

ok 1 number(s): "84562124"

Subtask #8:

score: 14
Accepted

Test #22:

score: 14
Accepted
time: 572ms
memory: 133232kb

input:

94060593399194 1

output:

52991150 887133157

result:

ok 2 number(s): "52991150 887133157"

Test #23:

score: 14
Accepted
time: 601ms
memory: 133696kb

input:

98527940728119 1

output:

281611635 910356955

result:

ok 2 number(s): "281611635 910356955"

Test #24:

score: 14
Accepted
time: 555ms
memory: 127936kb

input:

90501814019947 1

output:

666385143 229785369

result:

ok 2 number(s): "666385143 229785369"

Subtask #9:

score: 0
Runtime Error

Test #25:

score: 0
Runtime Error

input:

9772457586483846 0

output:

result:

Subtask #10:

score: 17
Accepted

Test #31:

score: 17
Accepted
time: 1810ms
memory: 319100kb

input:

949243849085176 1

output:

508465534 771553755

result:

ok 2 number(s): "508465534 771553755"

Test #32:

score: 17
Accepted
time: 1804ms
memory: 313716kb

input:

924225524519163 1

output:

867410272 870831653

result:

ok 2 number(s): "867410272 870831653"

Test #33:

score: 17
Accepted
time: 1862ms
memory: 321832kb

input:

978079151303393 1

output:

235076358 675828942

result:

ok 2 number(s): "235076358 675828942"

Test #34:

score: 17
Accepted
time: 1770ms
memory: 316820kb

input:

929804617107620 1

output:

790604296 73162158

result:

ok 2 number(s): "790604296 73162158"

Test #35:

score: 17
Accepted
time: 1892ms
memory: 323340kb

input:

989806727450552 1

output:

378550840 783149232

result:

ok 2 number(s): "378550840 783149232"
English 繁體中文 简体中文

Server Time: 2024-12-05 01:32:34 | OpenSource Project