QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#802544#9867. FlowersTranscend Lights (Qiwen Xu, Nuo Chen, Fanyou He)#AC ✓93ms11964kbC++231.2kb2024-12-07 13:58:542024-12-07 13:58:55

Judging History

This is the latest submission verdict.

  • [2024-12-07 13:58:55]
  • Judged
  • Verdict: AC
  • Time: 93ms
  • Memory: 11964kb
  • [2024-12-07 13:58:54]
  • Submitted

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