Syx 刚学 OI，求助简单素数筛

常规
1 
#include <iostream>
#include <cstring>
using namespace std;
namespace Syxqwq {
	inline int read() {
		int x = 0, s = 1;
		char c = getchar();
		while (c > '9' || c < '0') {
			if (c == '-') s = -1;
			c = getchar();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c - '0');
			c = getchar();
		}
		return x * s;
	}
	void Write(int x) {
		if (x < 0) {
			putchar('-');
			x = -x;
		}
		if (x > 9) Write(x / 10);
		putchar(x % 10 + '0');
	}
	inline void write(int x, char c) {
		Write(x), putchar(c);
	}
}
using namespace Syxqwq;
bool isprime[500050];
int prime[500050], len;
void getprime() {
	int n = 5e5;
	memset(isprime, 1, sizeof isprime);
	isprime[0] = isprime[1] = 0;
	for (int i = 2; i <= n; ++i) {
		if (isprime[i]) prime[++len] = i;
		for (int j = 1; j <= len && i * prime[j] <= n; ++j) {
			isprime[i * prime[j]] = 0;
			if (i % prime[j] == 0) break;
		}
	}
}
const int N = 2e6 + 19;
int ans[N];
int main() {
	getprime();
	int n = read(), q = read();
	for (int i = 1; i <= n; ++i) {
		if (isprime[i]) ans[i] = 1;
		else {
			int j = i;
			for (int k = 1; j != 1; ++k) {
				if (j % prime[k] == 0){
					ans[i] += ans[prime[k]];
					while (j % prime[k] == 0) j /= prime[k];
				}
			}
		}
	}
	while (q--) {
		int ques = read();
		write(ans[ques], '\n');
	}
	return 0;
}

image
image937×908 20.2 KB

1 个赞
2

哦我脑子出问题了，是 j \div i 是素数hhh

1 个赞
3

还是挂了

#include <iostream>
#include <cstring>
using namespace std;
namespace Syxqwq {
	inline int read() {
		int x = 0, s = 1;
		char c = getchar();
		while (c > '9' || c < '0') {
			if (c == '-') s = -1;
			c = getchar();
		}
		while (c >= '0' && c <= '9') {
			x = (x << 1) + (x << 3) + (c - '0');
			c = getchar();
		}
		return x * s;
	}
	void Write(int x) {
		if (x < 0) {
			putchar('-');
			x = -x;
		}
		if (x > 9) Write(x / 10);
		putchar(x % 10 + '0');
	}
	inline void write(int x, char c) {
		Write(x), putchar(c);
	}
}
using namespace Syxqwq;
bool isprime[500050];
int prime[500050], len;
void getprime() {
	int n = 5e5;
	memset(isprime, 1, sizeof isprime);
	isprime[0] = isprime[1] = 0;
	for (int i = 2; i <= n; ++i) {
		if (isprime[i]) prime[++len] = i;
		for (int j = 1; j <= len && i * prime[j] <= n; ++j) {
			isprime[i * prime[j]] = 0;
			if (i % prime[j] == 0) break;
		}
	}
}
const int N = 2e6 + 19;
int ans[N];
int main() {
	getprime();
	int n = read(), q = read();
	ans[1] = 1;
	for (int i = 2; i <= n; ++i) {
		if (isprime[i]) ans[i] = 1;
		else {
			int j = i;
			for (int k = 1; j != 1; ++k) {
				if (j % prime[k] == 0){
					while (j % prime[k] == 0) j /= prime[k];
					if (j == 1 || isprime[j]) ans[i] += ans[j];
                    ans[i] %= 1000000007;
				}
			}
		}
	}
	while (q--) {
		int ques = read();
		write(ans[ques], '\n');
	}
	return 0;
}
1 个赞
4

过掉了，降智了

2 个赞
5

666

1 个赞
6

dalao不行啊
‘

1 个赞
7

经典刚学OI

经典40分钟AK(

2 个赞
8

洛谷红名大佬在线装弱

1 个赞
9

他大号排名49，小号排名965，全是红名

1 个赞
10

66666666666666666666666666666666

1 个赞