QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#918526 | #9867. Flowers | JEdward | AC ✓ | 94ms | 10344kb | C++20 | 2.9kb | 2025-02-27 21:11:28 | 2025-02-27 21:11:33 |
Judging History
answer
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0), cin.tie(0)
#define int long long
#define ppc __builtin_popcount
#define endl '\n'
#define lowbit(x) (x & -x)
#define all(s) s.begin(), s.end()
#define pii pair<int,int>
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define here system("pause")
using namespace std;
template <class T>
inline void read(T &x){
x = 0;
char c = getchar();
bool f = 0;
for (; !isdigit(c); c = getchar()) f ^= (c == '-');
for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
x = f ? -x : x;
}
template <class T>
inline void write(T x){
if (x < 0) putchar('-'), x = -x;
if (x < 10) putchar(x + 48);
else write(x / 10), putchar(x % 10 + 48);
}
template<typename T> void chkmin(T& lhs, const T& rhs) { lhs = lhs > rhs ? rhs : lhs; }
template<typename T> void chkmax(T& lhs, const T& rhs) { lhs = lhs < rhs ? rhs : lhs; }
const int N = 2e5 + 4;
const int INF = 8e18 + 9;
const double eps = 1e-9;
const double Pi = acos(-1);
inline int pow(int a, int b, int p){ int res = 1%p; while(b){ if(b&1) res=res*a%p; a=a*a%p, b>>=1;} return res;}
inline int inv(int a, int p){ return pow(a,p-2,p)%p;}
mt19937 rnd(chrono::duration_cast<chrono::nanoseconds>(chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
uniform_int_distribution<int> dist(L, R);
return dist(rnd);
}
int n, m, mod;
int sq;
bool vis[N];
int primes[N], cnt;
int w[N], g[N];
int id1[N], id2[N];
int ans[15];
void init() {
vis[1] = 1;
for (int i = 2; i <= sq; i++) {
if (!vis[i]) primes[++cnt] = i;
for (int j = 1; j <= cnt && primes[j] <= sq / i; j++) {
vis[i * primes[j]] = 1;
if (i % primes[j] == 0) break;
}
}
}
inline int get(int x) {
if (x < N) return id1[x];
return id2[n / x];
}
void dfs(int u, int x, int w) {
if (primes[u] > x) return;
ans[w + 1] += g[get(x)] - u;
for (int i = u + 1; i <= cnt && primes[i] * primes[i] <= x; i++) {
for (int 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);
}
}
}
signed main() {
IOS;
cin >> n >> mod;
sq = sqrt(n);
while ((sq + 1) * (sq + 1) <= n) sq++;
while (sq * sq > n) sq--;
init();
for (int l = 1, r; l <= n; l = r + 1) {
int v = n / l;
r = n / v;
w[++m] = v;
if (v < N) 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 && primes[i] * primes[i] <= w[j]; j++) {
g[j] -= g[get(w[j] / primes[i])] - (i - 1);
}
}
dfs(0, n, 0);
int res = 1;
for (int i = 2; i <= 10; i++) {
res = res * pow(i, ans[i], mod) % mod;
}
cout << res << '\n';
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7792kb
input:
5 998244353
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7792kb
input:
10 998244353
output:
4
result:
ok 1 number(s): "4"
Test #3:
score: 0
Accepted
time: 91ms
memory: 8988kb
input:
10000000000 998244353
output:
889033323
result:
ok 1 number(s): "889033323"
Test #4:
score: 0
Accepted
time: 0ms
memory: 7792kb
input:
114514 690913931
output:
324700175
result:
ok 1 number(s): "324700175"
Test #5:
score: 0
Accepted
time: 0ms
memory: 7800kb
input:
1919180 834093847
output:
646537851
result:
ok 1 number(s): "646537851"
Test #6:
score: 0
Accepted
time: 0ms
memory: 7796kb
input:
906389 647338613
output:
169737221
result:
ok 1 number(s): "169737221"
Test #7:
score: 0
Accepted
time: 0ms
memory: 7928kb
input:
984569 661772093
output:
538193748
result:
ok 1 number(s): "538193748"
Test #8:
score: 0
Accepted
time: 0ms
memory: 7792kb
input:
929116 593924027
output:
205577710
result:
ok 1 number(s): "205577710"
Test #9:
score: 0
Accepted
time: 0ms
memory: 8052kb
input:
973649 756926927
output:
110478509
result:
ok 1 number(s): "110478509"
Test #10:
score: 0
Accepted
time: 0ms
memory: 7796kb
input:
952730 517371427
output:
369025161
result:
ok 1 number(s): "369025161"
Test #11:
score: 0
Accepted
time: 0ms
memory: 7612kb
input:
996362 731032373
output:
598082216
result:
ok 1 number(s): "598082216"
Test #12:
score: 0
Accepted
time: 0ms
memory: 7792kb
input:
994582 680360567
output:
196510965
result:
ok 1 number(s): "196510965"
Test #13:
score: 0
Accepted
time: 90ms
memory: 10208kb
input:
9807161842 610831159
output:
153249139
result:
ok 1 number(s): "153249139"
Test #14:
score: 0
Accepted
time: 85ms
memory: 10296kb
input:
9169908183 701443451
output:
324649616
result:
ok 1 number(s): "324649616"
Test #15:
score: 0
Accepted
time: 86ms
memory: 8724kb
input:
9201785456 640300459
output:
397372089
result:
ok 1 number(s): "397372089"
Test #16:
score: 0
Accepted
time: 89ms
memory: 8948kb
input:
9740261856 956479159
output:
176750230
result:
ok 1 number(s): "176750230"
Test #17:
score: 0
Accepted
time: 22ms
memory: 8172kb
input:
1359090224 992341157
output:
923341100
result:
ok 1 number(s): "923341100"
Test #18:
score: 0
Accepted
time: 29ms
memory: 7996kb
input:
2001052730 763501463
output:
562415935
result:
ok 1 number(s): "562415935"
Test #19:
score: 0
Accepted
time: 47ms
memory: 8412kb
input:
3905939101 828044311
output:
500302420
result:
ok 1 number(s): "500302420"
Test #20:
score: 0
Accepted
time: 52ms
memory: 8548kb
input:
4638306389 770966029
output:
436075816
result:
ok 1 number(s): "436075816"
Test #21:
score: 0
Accepted
time: 58ms
memory: 9056kb
input:
5420730405 818828191
output:
35679557
result:
ok 1 number(s): "35679557"
Test #22:
score: 0
Accepted
time: 70ms
memory: 8580kb
input:
6909084541 736712321
output:
307308305
result:
ok 1 number(s): "307308305"
Test #23:
score: 0
Accepted
time: 75ms
memory: 8752kb
input:
7857218570 793606399
output:
139036999
result:
ok 1 number(s): "139036999"
Test #24:
score: 0
Accepted
time: 80ms
memory: 9400kb
input:
8134885470 553667887
output:
209895871
result:
ok 1 number(s): "209895871"
Test #25:
score: 0
Accepted
time: 93ms
memory: 10344kb
input:
10000000000 966627661
output:
788042772
result:
ok 1 number(s): "788042772"
Test #26:
score: 0
Accepted
time: 0ms
memory: 7788kb
input:
1 998244853
output:
1
result:
ok 1 number(s): "1"
Test #27:
score: 0
Accepted
time: 0ms
memory: 9836kb
input:
2 998244853
output:
1
result:
ok 1 number(s): "1"
Test #28:
score: 0
Accepted
time: 0ms
memory: 9836kb
input:
3 998244853
output:
1
result:
ok 1 number(s): "1"
Test #29:
score: 0
Accepted
time: 1ms
memory: 7772kb
input:
4 998244853
output:
1
result:
ok 1 number(s): "1"
Test #30:
score: 0
Accepted
time: 94ms
memory: 8708kb
input:
10000000000 101453381
output:
91945195
result:
ok 1 number(s): "91945195"
Test #31:
score: 0
Accepted
time: 90ms
memory: 8860kb
input:
10000000000 101530493
output:
19287261
result:
ok 1 number(s): "19287261"
Extra Test:
score: 0
Extra Test Passed