QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#808449#9867. Flowers通顶雪道 (Qiuyang Mang, Youran Sun, Qingshuo Guo)AC ✓91ms12440kbC++141.2kb2024-12-10 20:52:242024-12-10 20:52:25

Judging History

This is the latest submission verdict.

  • [2024-12-10 20:52:25]
  • Judged
  • Verdict: AC
  • Time: 91ms
  • Memory: 12440kb
  • [2024-12-10 20:52:24]
  • 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: 10088kb

input:

5 998244353

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 1ms
memory: 7984kb

input:

10 998244353

output:

4

result:

ok 1 number(s): "4"

Test #3:

score: 0
Accepted
time: 91ms
memory: 10508kb

input:

10000000000 998244353

output:

889033323

result:

ok 1 number(s): "889033323"

Test #4:

score: 0
Accepted
time: 2ms
memory: 11980kb

input:

114514 690913931

output:

324700175

result:

ok 1 number(s): "324700175"

Test #5:

score: 0
Accepted
time: 0ms
memory: 12132kb

input:

1919180 834093847

output:

646537851

result:

ok 1 number(s): "646537851"

Test #6:

score: 0
Accepted
time: 0ms
memory: 10012kb

input:

906389 647338613

output:

169737221

result:

ok 1 number(s): "169737221"

Test #7:

score: 0
Accepted
time: 2ms
memory: 12136kb

input:

984569 661772093

output:

538193748

result:

ok 1 number(s): "538193748"

Test #8:

score: 0
Accepted
time: 0ms
memory: 12136kb

input:

929116 593924027

output:

205577710

result:

ok 1 number(s): "205577710"

Test #9:

score: 0
Accepted
time: 2ms
memory: 10068kb

input:

973649 756926927

output:

110478509

result:

ok 1 number(s): "110478509"

Test #10:

score: 0
Accepted
time: 0ms
memory: 9884kb

input:

952730 517371427

output:

369025161

result:

ok 1 number(s): "369025161"

Test #11:

score: 0
Accepted
time: 1ms
memory: 9836kb

input:

996362 731032373

output:

598082216

result:

ok 1 number(s): "598082216"

Test #12:

score: 0
Accepted
time: 1ms
memory: 9884kb

input:

994582 680360567

output:

196510965

result:

ok 1 number(s): "196510965"

Test #13:

score: 0
Accepted
time: 85ms
memory: 10828kb

input:

9807161842 610831159

output:

153249139

result:

ok 1 number(s): "153249139"

Test #14:

score: 0
Accepted
time: 86ms
memory: 10592kb

input:

9169908183 701443451

output:

324649616

result:

ok 1 number(s): "324649616"

Test #15:

score: 0
Accepted
time: 83ms
memory: 10824kb

input:

9201785456 640300459

output:

397372089

result:

ok 1 number(s): "397372089"

Test #16:

score: 0
Accepted
time: 89ms
memory: 10616kb

input:

9740261856 956479159

output:

176750230

result:

ok 1 number(s): "176750230"

Test #17:

score: 0
Accepted
time: 19ms
memory: 10292kb

input:

1359090224 992341157

output:

923341100

result:

ok 1 number(s): "923341100"

Test #18:

score: 0
Accepted
time: 26ms
memory: 11984kb

input:

2001052730 763501463

output:

562415935

result:

ok 1 number(s): "562415935"

Test #19:

score: 0
Accepted
time: 43ms
memory: 10580kb

input:

3905939101 828044311

output:

500302420

result:

ok 1 number(s): "500302420"

Test #20:

score: 0
Accepted
time: 45ms
memory: 10336kb

input:

4638306389 770966029

output:

436075816

result:

ok 1 number(s): "436075816"

Test #21:

score: 0
Accepted
time: 55ms
memory: 10480kb

input:

5420730405 818828191

output:

35679557

result:

ok 1 number(s): "35679557"

Test #22:

score: 0
Accepted
time: 70ms
memory: 11944kb

input:

6909084541 736712321

output:

307308305

result:

ok 1 number(s): "307308305"

Test #23:

score: 0
Accepted
time: 77ms
memory: 10520kb

input:

7857218570 793606399

output:

139036999

result:

ok 1 number(s): "139036999"

Test #24:

score: 0
Accepted
time: 75ms
memory: 12440kb

input:

8134885470 553667887

output:

209895871

result:

ok 1 number(s): "209895871"

Test #25:

score: 0
Accepted
time: 91ms
memory: 10540kb

input:

10000000000 966627661

output:

788042772

result:

ok 1 number(s): "788042772"

Test #26:

score: 0
Accepted
time: 2ms
memory: 11920kb

input:

1 998244853

output:

1

result:

ok 1 number(s): "1"

Test #27:

score: 0
Accepted
time: 0ms
memory: 10088kb

input:

2 998244853

output:

1

result:

ok 1 number(s): "1"

Test #28:

score: 0
Accepted
time: 1ms
memory: 7836kb

input:

3 998244853

output:

1

result:

ok 1 number(s): "1"

Test #29:

score: 0
Accepted
time: 1ms
memory: 7952kb

input:

4 998244853

output:

1

result:

ok 1 number(s): "1"

Test #30:

score: 0
Accepted
time: 91ms
memory: 12148kb

input:

10000000000 101453381

output:

91945195

result:

ok 1 number(s): "91945195"

Test #31:

score: 0
Accepted
time: 87ms
memory: 10396kb

input:

10000000000 101530493

output:

19287261

result:

ok 1 number(s): "19287261"

Extra Test:

score: 0
Extra Test Passed