QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#918526#9867. FlowersJEdwardAC ✓94ms10344kbC++202.9kb2025-02-27 21:11:282025-02-27 21:11:33

Judging History

This is the latest submission verdict.

  • [2025-02-27 21:11:33]
  • Judged
  • Verdict: AC
  • Time: 94ms
  • Memory: 10344kb
  • [2025-02-27 21:11:28]
  • Submitted

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