求本代码的时间复杂度(以AC)
  • 板块P1375 小猫
  • 楼主_111_
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/5/6 19:50
  • 上次更新2023/10/23 16:30:24
查看原帖
求本代码的时间复杂度(以AC)
526713
_111_楼主2023/5/6 19:50
#include <bits/stdc++.h>

using namespace std;
const int N = 200010, mod = 1000000007;
int a[N];
int n, cnt = 0;
int prime[N];
bool vis[N];
void Get_prime(){
	for (int i = 2; i <= 2 * n; i++) {
		if (!vis[i]) {
			prime[++cnt] = i;
		}
		for (int j = 1; i * prime[j] <= 2 * n && j <= cnt; j++) {
			vis[i * prime[j]] = 1;
			if (i % prime[j] == 0) {
				break;
			}
		}
	}
}
int main() {
	scanf("%d", &n);
	Get_prime();
	for (int i = 2 * n; i >= n + 1; i--) {
		int x = i;
		for (int j = 1; j <= cnt && prime[j] <= x; j++) {
			if (x % prime[j] == 0) {
				while (x % prime[j] == 0) {
					x /= prime[j];
					a[j]++;
				}
			}
		}
	}
	for (int i = 2; i <= n + 1; i++) {
		int x = i;
		for (int j = 1; j <= cnt && prime[j] <= x; j++) {
			if (x % prime[j] == 0) {
				while (x % prime[j] == 0) {
					x /= prime[j];
					a[j]--;
				}
			}
		}
	}
	long long ans = 1;
	for (int i = 1; i <= cnt; i++) {
		if (a[i]) {
			while (a[i]--) {
				ans = (ans * prime[i]) % mod; 
			}
		}
	}
	printf("%d", ans);
	return 0;
}
2023/5/6 19:50
加载中...