QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #451243 | #8761. 另一个计数问题 | tarjen# | TL | 1609ms | 18464kb | C++20 | 1.4kb | 2024-06-22 23:43:59 | 2024-06-22 23:43:59 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const ll Ny2=(mod+1)/2;
const ll Ny6=166374059;
const int maxn=1e6+10;
ll pr[maxn],prs[maxn],prs2[maxn],cnt=0,f[maxn];
void add(ll &x,ll y){
if((x+=y)>=mod)x-=mod;
}
void del(ll &x,ll y){
if((x-=y)<0)x+=mod;
}
ll Sum(ll x){
x%=mod;
return x*(x+1)%mod*Ny2%mod;
}
ll S(ll x,int m){
while(pr[m]*pr[m]>x)m--;
if(m==0)return (Sum(x)-1+mod)%mod;
ll res=S(x,m-1);
del(res,pr[m]*((S(x/pr[m],m-1)-prs[m-1]+mod)%mod)%mod);
return res;
}
ll Sum2(ll x){
x%=mod;
return x*(x+1)%mod*(2*x+1)%mod*Ny6%mod;
}
ll S2(ll x,int m){
while(pr[m]*pr[m]>x)m--;
if(m==0)return (Sum2(x)-1+mod)%mod;
ll res=S2(x,m-1);
del(res,pr[m]*pr[m]%mod*((S2(x/pr[m],m-1)-prs2[m-1]+mod)%mod)%mod);
return res;
}
signed main()
{
for(ll i=2;i<maxn;i++)if(!f[i]){
cnt++;pr[cnt]=i;
prs[cnt]=(prs[cnt-1]+i)%mod;
prs2[cnt]=(prs2[cnt-1]+i*i%mod)%mod;
for(int j=i+i;j<maxn;j+=i)f[j]=1;
}
ll n;cin>>n;
ll p1=(S(n,cnt)-S(n/2,cnt)+mod)%mod;
ll p2=(S2(n,cnt)-S2(n/2,cnt)+mod)%mod;
ll z=(Sum(n)-1)*(Sum(n)-1)%mod;
// cout<<"z="<<z<<" p1="<<p1<<" p2="<<p2<<endl;
z=(z-(Sum(n)-1)*p1%mod-(Sum(n)-1-p1)*p1%mod+2*mod)%mod;
// cout<<"z="<<z<<endl;
z=(z+p2)%mod;
z=(z-(Sum2(n)-1)+mod)%mod;
z=z*Ny2%mod;
cout<<z;
// ll ans=0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 12ms
memory: 18300kb
input:
4
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 10ms
memory: 14720kb
input:
5
output:
8
result:
ok 1 number(s): "8"
Test #3:
score: 0
Accepted
time: 3ms
memory: 18268kb
input:
6
output:
80
result:
ok 1 number(s): "80"
Test #4:
score: 0
Accepted
time: 7ms
memory: 14720kb
input:
7
output:
80
result:
ok 1 number(s): "80"
Test #5:
score: 0
Accepted
time: 10ms
memory: 14668kb
input:
8
output:
200
result:
ok 1 number(s): "200"
Test #6:
score: 0
Accepted
time: 6ms
memory: 14716kb
input:
9
output:
407
result:
ok 1 number(s): "407"
Test #7:
score: 0
Accepted
time: 7ms
memory: 16716kb
input:
10
output:
937
result:
ok 1 number(s): "937"
Test #8:
score: 0
Accepted
time: 10ms
memory: 16556kb
input:
79
output:
3224298
result:
ok 1 number(s): "3224298"
Test #9:
score: 0
Accepted
time: 8ms
memory: 16376kb
input:
123
output:
21077222
result:
ok 1 number(s): "21077222"
Test #10:
score: 0
Accepted
time: 4ms
memory: 18212kb
input:
158
output:
57411585
result:
ok 1 number(s): "57411585"
Test #11:
score: 0
Accepted
time: 11ms
memory: 18240kb
input:
285
output:
605750829
result:
ok 1 number(s): "605750829"
Test #12:
score: 0
Accepted
time: 4ms
memory: 18088kb
input:
355
output:
509863120
result:
ok 1 number(s): "509863120"
Test #13:
score: 0
Accepted
time: 4ms
memory: 18348kb
input:
484
output:
311440260
result:
ok 1 number(s): "311440260"
Test #14:
score: 0
Accepted
time: 11ms
memory: 14652kb
input:
520
output:
102191845
result:
ok 1 number(s): "102191845"
Test #15:
score: 0
Accepted
time: 6ms
memory: 14720kb
input:
706
output:
300787918
result:
ok 1 number(s): "300787918"
Test #16:
score: 0
Accepted
time: 12ms
memory: 18260kb
input:
747
output:
505062591
result:
ok 1 number(s): "505062591"
Test #17:
score: 0
Accepted
time: 7ms
memory: 16400kb
input:
784
output:
181810798
result:
ok 1 number(s): "181810798"
Test #18:
score: 0
Accepted
time: 7ms
memory: 18044kb
input:
76879
output:
716166793
result:
ok 1 number(s): "716166793"
Test #19:
score: 0
Accepted
time: 11ms
memory: 16804kb
input:
209295
output:
753032272
result:
ok 1 number(s): "753032272"
Test #20:
score: 0
Accepted
time: 7ms
memory: 14660kb
input:
220895
output:
874612082
result:
ok 1 number(s): "874612082"
Test #21:
score: 0
Accepted
time: 11ms
memory: 16796kb
input:
243390
output:
68635874
result:
ok 1 number(s): "68635874"
Test #22:
score: 0
Accepted
time: 4ms
memory: 16780kb
input:
414767
output:
862578797
result:
ok 1 number(s): "862578797"
Test #23:
score: 0
Accepted
time: 11ms
memory: 14656kb
input:
431662
output:
231728766
result:
ok 1 number(s): "231728766"
Test #24:
score: 0
Accepted
time: 11ms
memory: 16664kb
input:
521130
output:
106207351
result:
ok 1 number(s): "106207351"
Test #25:
score: 0
Accepted
time: 12ms
memory: 18060kb
input:
668419
output:
580625063
result:
ok 1 number(s): "580625063"
Test #26:
score: 0
Accepted
time: 12ms
memory: 16436kb
input:
700378
output:
790849562
result:
ok 1 number(s): "790849562"
Test #27:
score: 0
Accepted
time: 4ms
memory: 16776kb
input:
965876
output:
856082142
result:
ok 1 number(s): "856082142"
Test #28:
score: 0
Accepted
time: 776ms
memory: 16684kb
input:
998244350
output:
539142456
result:
ok 1 number(s): "539142456"
Test #29:
score: 0
Accepted
time: 779ms
memory: 16944kb
input:
998244351
output:
730264865
result:
ok 1 number(s): "730264865"
Test #30:
score: 0
Accepted
time: 778ms
memory: 14876kb
input:
998244352
output:
326703895
result:
ok 1 number(s): "326703895"
Test #31:
score: 0
Accepted
time: 782ms
memory: 14940kb
input:
998244353
output:
326703895
result:
ok 1 number(s): "326703895"
Test #32:
score: 0
Accepted
time: 778ms
memory: 18464kb
input:
998244354
output:
730264864
result:
ok 1 number(s): "730264864"
Test #33:
score: 0
Accepted
time: 776ms
memory: 14876kb
input:
998244355
output:
539142451
result:
ok 1 number(s): "539142451"
Test #34:
score: 0
Accepted
time: 780ms
memory: 16664kb
input:
998244356
output:
751581014
result:
ok 1 number(s): "751581014"
Test #35:
score: 0
Accepted
time: 1609ms
memory: 14872kb
input:
2165916141
output:
216013547
result:
ok 1 number(s): "216013547"
Test #36:
score: -100
Time Limit Exceeded
input:
3550627266