QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#817859 | #9867. Flowers | propane | AC ✓ | 91ms | 8536kb | C++20 | 2.0kb | 2024-12-17 13:45:54 | 2024-12-17 13:45:56 |
Judging History
answer
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
using namespace std;
using LL = long long;
const int maxn = 2e5 + 5;
LL n, mod;
int sq;
bool isPrime[maxn];
int primes[maxn], cnt;
void init(){
isPrime[1] = 1;
for(int i = 2; i <= sq; i++){
if (!isPrime[i]) primes[++cnt] = i;
for(int j = 1; i * primes[j] <= sq; j++){
isPrime[i * primes[j]] = 1;
if (i % primes[j] == 0) break;
}
}
}
LL w[maxn];
int m;
int id1[maxn], id2[maxn];
LL g[maxn];
int get(LL x){
if (x < maxn) return id1[x];
return id2[n / x];
}
LL qpow(LL a, LL b){
LL ans = 1;
while(b){
if (b & 1) ans = ans * a % mod;
b >>= 1;
a = a * a % mod;
}
return ans;
}
LL ans[15];
void dfs(int u, LL x, int w){
if (primes[u] > x) return;
ans[w + 1] += g[get(x)] - u;
for(int i = u + 1; i <= cnt and 1LL * primes[i] * primes[i] <= x; i++){
for(LL c = 1, pows = primes[i]; pows <= x; c += 1, pows *= primes[i]){
if (c > 1){
ans[w + 1] += 1;
}
dfs(i, x / pows, w + 1);
}
}
}
int main(){
#ifdef LOCAL
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
cin >> n >> mod;
sq = sqrt(n);
while(1LL * (sq + 1) * (sq + 1) <= n) sq++;
while(1LL * sq * sq > n) sq--;
init();
for(LL l = 1, r; l <= n; l = r + 1){
LL v = n / l;
r = n / v;
w[++m] = v;
if (v < maxn) id1[v] = m;
else id2[n / v] = m;
g[m] = v - 1;
}
for(int i = 1; i <= cnt; i++){
for(int j = 1; j <= m and 1LL * primes[i] * primes[i] <= w[j]; j++){
g[j] -= g[get(w[j] / primes[i])] - (i - 1);
}
}
dfs(0, n, 0);
LL res = 1;
for(int i = 2; i <= 10; i++){
res = res * qpow(i, ans[i]) % mod;
}
cout << res << '\n';
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 5540kb
input:
5 998244353
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 0ms
memory: 3532kb
input:
10 998244353
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 87ms
memory: 8424kb
input:
10000000000 998244353
output:
889033323
result:
ok 1 number(s): "889033323"
Test #4:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
114514 690913931
output:
324700175
result:
ok 1 number(s): "324700175"
Test #5:
score: 0
Accepted
time: 1ms
memory: 5972kb
input:
1919180 834093847
output:
646537851
result:
ok 1 number(s): "646537851"
Test #6:
score: 0
Accepted
time: 0ms
memory: 6004kb
input:
906389 647338613
output:
169737221
result:
ok 1 number(s): "169737221"
Test #7:
score: 0
Accepted
time: 0ms
memory: 5612kb
input:
984569 661772093
output:
538193748
result:
ok 1 number(s): "538193748"
Test #8:
score: 0
Accepted
time: 1ms
memory: 5600kb
input:
929116 593924027
output:
205577710
result:
ok 1 number(s): "205577710"
Test #9:
score: 0
Accepted
time: 1ms
memory: 5656kb
input:
973649 756926927
output:
110478509
result:
ok 1 number(s): "110478509"
Test #10:
score: 0
Accepted
time: 0ms
memory: 5660kb
input:
952730 517371427
output:
369025161
result:
ok 1 number(s): "369025161"
Test #11:
score: 0
Accepted
time: 1ms
memory: 5712kb
input:
996362 731032373
output:
598082216
result:
ok 1 number(s): "598082216"
Test #12:
score: 0
Accepted
time: 1ms
memory: 5700kb
input:
994582 680360567
output:
196510965
result:
ok 1 number(s): "196510965"
Test #13:
score: 0
Accepted
time: 89ms
memory: 8452kb
input:
9807161842 610831159
output:
153249139
result:
ok 1 number(s): "153249139"
Test #14:
score: 0
Accepted
time: 85ms
memory: 8356kb
input:
9169908183 701443451
output:
324649616
result:
ok 1 number(s): "324649616"
Test #15:
score: 0
Accepted
time: 85ms
memory: 8424kb
input:
9201785456 640300459
output:
397372089
result:
ok 1 number(s): "397372089"
Test #16:
score: 0
Accepted
time: 89ms
memory: 8312kb
input:
9740261856 956479159
output:
176750230
result:
ok 1 number(s): "176750230"
Test #17:
score: 0
Accepted
time: 19ms
memory: 7592kb
input:
1359090224 992341157
output:
923341100
result:
ok 1 number(s): "923341100"
Test #18:
score: 0
Accepted
time: 29ms
memory: 5892kb
input:
2001052730 763501463
output:
562415935
result:
ok 1 number(s): "562415935"
Test #19:
score: 0
Accepted
time: 48ms
memory: 7780kb
input:
3905939101 828044311
output:
500302420
result:
ok 1 number(s): "500302420"
Test #20:
score: 0
Accepted
time: 45ms
memory: 7796kb
input:
4638306389 770966029
output:
436075816
result:
ok 1 number(s): "436075816"
Test #21:
score: 0
Accepted
time: 59ms
memory: 6820kb
input:
5420730405 818828191
output:
35679557
result:
ok 1 number(s): "35679557"
Test #22:
score: 0
Accepted
time: 66ms
memory: 8116kb
input:
6909084541 736712321
output:
307308305
result:
ok 1 number(s): "307308305"
Test #23:
score: 0
Accepted
time: 76ms
memory: 8088kb
input:
7857218570 793606399
output:
139036999
result:
ok 1 number(s): "139036999"
Test #24:
score: 0
Accepted
time: 75ms
memory: 7464kb
input:
8134885470 553667887
output:
209895871
result:
ok 1 number(s): "209895871"
Test #25:
score: 0
Accepted
time: 91ms
memory: 7836kb
input:
10000000000 966627661
output:
788042772
result:
ok 1 number(s): "788042772"
Test #26:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
1 998244853
output:
1
result:
ok 1 number(s): "1"
Test #27:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
2 998244853
output:
1
result:
ok 1 number(s): "1"
Test #28:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
3 998244853
output:
1
result:
ok 1 number(s): "1"
Test #29:
score: 0
Accepted
time: 0ms
memory: 3584kb
input:
4 998244853
output:
1
result:
ok 1 number(s): "1"
Test #30:
score: 0
Accepted
time: 91ms
memory: 8536kb
input:
10000000000 101453381
output:
91945195
result:
ok 1 number(s): "91945195"
Test #31:
score: 0
Accepted
time: 91ms
memory: 8336kb
input:
10000000000 101530493
output:
19287261
result:
ok 1 number(s): "19287261"
Extra Test:
score: 0
Extra Test Passed