不要想复杂，第一题就是纯暴力
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
int main(void) {
int n, x; scanf ("%d%d", &n, &x);
int ans = 0;
for (int i=1; i<=n; ++i) {
if (x % i == 0) {
int y = x / i;
if (1 <= y && y <= n) ans++;
}
}
printf ("%d
", ans);
return 0;
}
题意：在1~n之间猜一个数字x，可以问一些问题，x是否能整除y，问最少要问多少问题才能确定x
分析：我的方法就是把2~n的数字的质因数筛选出来，由此可以判断一些素数和不同素数的乘积。但是这样遗漏了平方数，比如能确定x整除3，结果可能是3也可能是9，所以最后把质因数的幂也放进答案
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <set>
#include <map>
using namespace std;
const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f;
map<int, int> mp;
vector<int> ans;
bool is_prime(int x) {
if (x == 2 || x == 3) return true;
if (x % 6 != 1 && x % 6 != 5) return false;
for (int i=5; i*i<=x; i+=6) {
if (x % i == 0 || x % (i + 2) == 0) return false;
}
return true;
}
void factorize(int x) {
for (int i=2; i*i<=x; ++i) {
while (x % i == 0) {
if (!mp[x/i] && x / i != 1 && is_prime (x / i)) {
ans.push_back (x/i); mp[x/i] = 1;
}
x /= i;
}
}
if (x != 1) {
if (!mp[x] && is_prime (x)) {
ans.push_back (x); mp[x] = 1;
}
}
}
int main(void) {
int n; scanf ("%d", &n);
mp.clear (); ans.clear ();
for (int i=n; i>1; --i) {
factorize (i);
}
int sz = ans.size ();
for (int i=0; i<sz; ++i) {
int x = ans[i]; int t = x * x;
while (t <= n) {
if (!mp[t]) {
ans.push_back (t);
}
t *= x;
}
}
sort (ans.begin (), ans.end ());
sz = ans.size ();
printf ("%d
", sz);
for (int i=0; i<sz; ++i) {
printf ("%d%c", ans[i], i == sz - 1 ? '
' : ' ');
}
return 0;
}
DP+抽屉原理 B - Modulo Sum
题意：问n个数字能否选出几个数字使得它们的和能整除m
分析：我觉得这是C题的难度。首先能想到同余模定理，对每个数字先取模。当n <= m时，用dp做，dp[i][j] 表示前i个数字，和取模后为j的方案有没有，那么就像01背包一样对与ai 取或不取，结果是dp[n][0]
当n > m时，官方题解是说弄个前缀和，根据抽屉原理，一定存在suml == sumr，那么sum (l + 1, r） == 0，也就是一定是YES了，这个我不会证明。戳开别人的代码发现可以用set来记录suml sumrd的值，如果那么根据上述一定是YES。
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10;
const int M = 1e3 + 10;
const int INF = 0x3f3f3f3f;
int a[N];
bool dp[M][M];
set<int> S;
int main(void) {
int n, m; scanf ("%d%d", &n, &m);
for (int i=1; i<=n; ++i) {
scanf ("%d", &a[i]); a[i] %= m;
}
bool flag = false;
memset (dp, false, sizeof (dp));
if (n <= m) {
for (int i=1; i<=n; ++i) {
dp[i][a[i]] = true;
}
for (int i=2; i<=n; ++i) {
for (int j=0; j<m; ++j) {
dp[i][j] |= dp[i-1][j];
int pre = (j - a[i] + m) % m;
dp[i][j] |= dp[i-1][pre];
}
}
flag = dp[n][0];
}
else {
S.clear ();
int sum = 0;
for (int i=1; i<=n; ++i) {
sum = (sum + a[i]) % m;
if (S.find (sum) != S.end ()) flag = true;
S.insert (sum);
}
// flag = true;
}
puts (flag ? "YES" : "NO");
return 0;
}