QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#802544 | #9867. Flowers | Transcend Lights (Qiwen Xu, Nuo Chen, Fanyou He)# | AC ✓ | 93ms | 11964kb | C++23 | 1.2kb | 2024-12-07 13:58:54 | 2024-12-07 13:58:55 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll n,B;
int p[301000];
bool fl[301000];
int mod;
int qpow(int a,ll b){
int c=1;
for(;b;b>>=1){
if(b&1)c=1ll*a*c%mod;
a=1ll*a*a%mod;
}
return c;
}
int c;
ll id[301000],g[300100];
int ip1[301000],ip2[301000],o;
int ip(ll x){
if(x<=B)return ip1[x];
return ip2[n/x];
}
ll an[20];
void S(ll x,int e,int s){
if(x<=p[e])return;
an[s+1]+=g[ip(x)]-e;
for(int i=e+1;i<=c&&1ll*p[i]*p[i]<=x;i++){
ll P=p[i];
for(int j=1;P<=x;j++,P*=p[i]){
S(x/P,i,s+1);
if(j!=1)an[s+1]++;
}
}
}
int main(){
scanf("%lld%d",&n,&mod);B=(ll)sqrt(n);
for(int i=2;i<=B;i++){
if(!fl[i])p[++c]=i;
for(int j=1;i*p[j]<=B&&j<=c;j++){
fl[i*p[j]]=1;
if(!(i%p[j]))break;
}
}
for(ll i=1,j;i<=n;i=j+1){
j=n/(n/i);id[++o]=n/i;
g[o]=n/i-1;
if(n/i<=B)ip1[n/i]=o;
else ip2[n/(n/i)]=o;
}
for(int i=1;i<=c;i++){
for(int j=1;j<=o&&1ll*p[i]*p[i]<=id[j];j++){
int v=ip(id[j]/p[i]);
g[j]-=(g[v]-(i-1));
}
}
S(n,0,0);
int ans=1;
for(int i=2;i<=13;i++)ans=1ll*ans*qpow(i,an[i])%mod;
printf("%d",ans);
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 11944kb
input:
5 998244353
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 10124kb
input:
10 998244353
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 88ms
memory: 10752kb
input:
10000000000 998244353
output:
889033323
result:
ok 1 number(s): "889033323"
Test #4:
score: 0
Accepted
time: 1ms
memory: 8020kb
input:
114514 690913931
output:
324700175
result:
ok 1 number(s): "324700175"
Test #5:
score: 0
Accepted
time: 2ms
memory: 11964kb
input:
1919180 834093847
output:
646537851
result:
ok 1 number(s): "646537851"
Test #6:
score: 0
Accepted
time: 1ms
memory: 7872kb
input:
906389 647338613
output:
169737221
result:
ok 1 number(s): "169737221"
Test #7:
score: 0
Accepted
time: 1ms
memory: 8028kb
input:
984569 661772093
output:
538193748
result:
ok 1 number(s): "538193748"
Test #8:
score: 0
Accepted
time: 1ms
memory: 9968kb
input:
929116 593924027
output:
205577710
result:
ok 1 number(s): "205577710"
Test #9:
score: 0
Accepted
time: 1ms
memory: 8020kb
input:
973649 756926927
output:
110478509
result:
ok 1 number(s): "110478509"
Test #10:
score: 0
Accepted
time: 1ms
memory: 10124kb
input:
952730 517371427
output:
369025161
result:
ok 1 number(s): "369025161"
Test #11:
score: 0
Accepted
time: 0ms
memory: 10048kb
input:
996362 731032373
output:
598082216
result:
ok 1 number(s): "598082216"
Test #12:
score: 0
Accepted
time: 0ms
memory: 7820kb
input:
994582 680360567
output:
196510965
result:
ok 1 number(s): "196510965"
Test #13:
score: 0
Accepted
time: 87ms
memory: 10872kb
input:
9807161842 610831159
output:
153249139
result:
ok 1 number(s): "153249139"
Test #14:
score: 0
Accepted
time: 85ms
memory: 10780kb
input:
9169908183 701443451
output:
324649616
result:
ok 1 number(s): "324649616"
Test #15:
score: 0
Accepted
time: 85ms
memory: 10824kb
input:
9201785456 640300459
output:
397372089
result:
ok 1 number(s): "397372089"
Test #16:
score: 0
Accepted
time: 85ms
memory: 10328kb
input:
9740261856 956479159
output:
176750230
result:
ok 1 number(s): "176750230"
Test #17:
score: 0
Accepted
time: 19ms
memory: 10200kb
input:
1359090224 992341157
output:
923341100
result:
ok 1 number(s): "923341100"
Test #18:
score: 0
Accepted
time: 29ms
memory: 10324kb
input:
2001052730 763501463
output:
562415935
result:
ok 1 number(s): "562415935"
Test #19:
score: 0
Accepted
time: 47ms
memory: 10176kb
input:
3905939101 828044311
output:
500302420
result:
ok 1 number(s): "500302420"
Test #20:
score: 0
Accepted
time: 45ms
memory: 10524kb
input:
4638306389 770966029
output:
436075816
result:
ok 1 number(s): "436075816"
Test #21:
score: 0
Accepted
time: 55ms
memory: 10508kb
input:
5420730405 818828191
output:
35679557
result:
ok 1 number(s): "35679557"
Test #22:
score: 0
Accepted
time: 70ms
memory: 10412kb
input:
6909084541 736712321
output:
307308305
result:
ok 1 number(s): "307308305"
Test #23:
score: 0
Accepted
time: 72ms
memory: 10676kb
input:
7857218570 793606399
output:
139036999
result:
ok 1 number(s): "139036999"
Test #24:
score: 0
Accepted
time: 78ms
memory: 10444kb
input:
8134885470 553667887
output:
209895871
result:
ok 1 number(s): "209895871"
Test #25:
score: 0
Accepted
time: 88ms
memory: 10404kb
input:
10000000000 966627661
output:
788042772
result:
ok 1 number(s): "788042772"
Test #26:
score: 0
Accepted
time: 1ms
memory: 8016kb
input:
1 998244853
output:
1
result:
ok 1 number(s): "1"
Test #27:
score: 0
Accepted
time: 1ms
memory: 10060kb
input:
2 998244853
output:
1
result:
ok 1 number(s): "1"
Test #28:
score: 0
Accepted
time: 1ms
memory: 10120kb
input:
3 998244853
output:
1
result:
ok 1 number(s): "1"
Test #29:
score: 0
Accepted
time: 1ms
memory: 10128kb
input:
4 998244853
output:
1
result:
ok 1 number(s): "1"
Test #30:
score: 0
Accepted
time: 90ms
memory: 10428kb
input:
10000000000 101453381
output:
91945195
result:
ok 1 number(s): "91945195"
Test #31:
score: 0
Accepted
time: 93ms
memory: 10448kb
input:
10000000000 101530493
output:
19287261
result:
ok 1 number(s): "19287261"
Extra Test:
score: 0
Extra Test Passed