QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#572829#9309. Graph000226WA 40ms16748kbC++172.4kb2024-09-18 16:31:412024-09-18 16:31:41

Judging History

你现在查看的是最新测评结果

  • [2024-09-18 16:31:41]
  • 评测
  • 测评结果:WA
  • 用时:40ms
  • 内存:16748kb
  • [2024-09-18 16:31:41]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

#define lep(i, l, r) for(int i = (l); i <= (r); i ++)
#define rep(i, l, r) for(int i = (l); i >= (r); i --)
#define Lep(i, l, r) for(int i = (l); i <  (r); i ++)
#define debug(...) fprintf (stderr, __VA_ARGS__)
//#define int long long
using i64 = long long;
using ld = long double;
using ui64 = unsigned long long;

const int P = 998244353;
inline int mod(int x) { return x + (x >> 31 & P); }
inline void pls(int &x, int y) { x = mod(x + y - P); }
inline void sub(int &x, int y) { x = mod(x - y); }
inline int  add(int x, int y) { return mod (x + y - P); }
inline int  dec(int x, int y) { return mod (x - y); }

inline int power(int x, i64 k) {
	int res = 1;
	while(k) {
		if (k & 1) res = 1ll * res * x % P;
		x = 1ll * x * x % P; k >>= 1;
	} return res;
}

namespace Min25 {

	#define LL long long

	LL n;

	const int N = 1e6 + 10;

	int vis[N], p[N], tot;

	void init(int n = 1e6) {
		for(int i = 2; i <= n; i ++) {
			if(! vis[i]) p[++ tot] = i;
			for(int j = 1; p[j] * i <= n && j <= tot; j ++) {
				vis[i * p[j]] = 1;
				if(i % p[j] == 0) break;
			}
		}
	}

	int id0[N], id1[N];
	LL val[N];
	int num, sqr;
	LL g[N];

	inline int pos(LL x) {
		if(x <= sqr) return id0[x];
		else return id1[n / x];
	}

	i64 qry (i64 x) {
		if (x == 0) return 0;
		if (x <= sqr) return g[id0[x]];
		else return g[id1[n / x]];
	}

	void main(i64 _n) {
		
		n = _n;
		sqr = sqrt(n) + 1;
		init(sqr);
		for(LL l = 1, r = 1; l <= n; l = r = r + 1) {
			LL tmp = n / l;
			r = n / tmp;
			val[++ num] = tmp;
			if(tmp <= sqr) id0[tmp] = num;
			else id1[n / tmp] = num;
		}
		for(int i = 1; i <= num; i ++) g[i] = val[i] - 1;
		
		for(int j = 1; j <= tot; j ++) {
			int pj = p[j];
			for(int i = 1; i <= num; i ++) {
				if(val[i] / pj < pj) break;
				g[i] = g[i] - g[pos(val[i] / pj)] + j - 1;
			}
		}
		
		//cout << g[1] << endl;
		//return 0;
	}
}

i64 n;

inline int f(i64 m) {
	if (m <= 2) return 1;
	if (m == 3) return 3;
	// calc [m / 2 + 1, m]
	i64 cnt = Min25 :: qry(m) - Min25 :: qry(m / 2);
	
	return (m - cnt - 1) % P * power (m, cnt % (P - 1)) % P;
}

int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	Min25 :: main(n);
	i64 ans = 1;
	for (i64 l = 1, r; l <= n; l = r + 1) {
		r = n / (n / l);
		ans = 1ll * ans * power (f(n / l), r - l + 1) % P;
	}
	cout << ans << '\n';
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 9812kb

input:

4

output:

8

result:

ok answer is '8'

Test #2:

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

input:

2

output:

1

result:

ok answer is '1'

Test #3:

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

input:

123

output:

671840470

result:

ok answer is '671840470'

Test #4:

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

input:

233

output:

353738465

result:

ok answer is '353738465'

Test #5:

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

input:

5981

output:

970246821

result:

ok answer is '970246821'

Test #6:

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

input:

86422

output:

897815688

result:

ok answer is '897815688'

Test #7:

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

input:

145444

output:

189843901

result:

ok answer is '189843901'

Test #8:

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

input:

901000

output:

819449452

result:

ok answer is '819449452'

Test #9:

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

input:

1000000

output:

113573943

result:

ok answer is '113573943'

Test #10:

score: 0
Accepted
time: 3ms
memory: 11908kb

input:

23333333

output:

949849384

result:

ok answer is '949849384'

Test #11:

score: 0
Accepted
time: 4ms
memory: 10020kb

input:

102850434

output:

604886751

result:

ok answer is '604886751'

Test #12:

score: 0
Accepted
time: 15ms
memory: 10468kb

input:

998244353

output:

0

result:

ok answer is '0'

Test #13:

score: 0
Accepted
time: 16ms
memory: 12544kb

input:

1000000007

output:

318420284

result:

ok answer is '318420284'

Test #14:

score: 0
Accepted
time: 20ms
memory: 12604kb

input:

2147483547

output:

688759898

result:

ok answer is '688759898'

Test #15:

score: -100
Wrong Answer
time: 40ms
memory: 16748kb

input:

5120103302

output:

384994873

result:

wrong answer expected '116870489', found '384994873'