bzoj 1053
比较经典的一道题。
首先要观察出一些结论
（1）质数不超过10个。前十个质数相乘已经超过最大值。
（2）质数的指数是递减的。如果不是，可以把指数小的和大的交换一下，答案更小。
然后就搜索就好了。
这是一类数论+搜索的题目，要从题目看出一些剪枝，然后搜索即可。
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
ll a[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
ll n, ans, num;void dfs(int i, ll now, ll cnt, ll sum)
{if(i == 11) return;ll t = 1;_for(j, 1, cnt){t *= a[i];ll cur = now * t;if(cur > n) return;if(sum * (j + 1) == num && cur < ans)ans = cur, num = sum * (j + 1);else if(sum * (j + 1) > num)ans = cur, num = sum * (j + 1);dfs(i + 1, cur, j, sum * (j + 1));}
}int main()
{scanf("%lld", &n);dfs(1, 1, 31, 1);printf("%lld\n", ans);return 0;
}bzoj 1257
这道题用到了一个很重要的结论
任意i属于[i, k / (k / i)], k / i的值相等（除法均是向下取整）
那么我们把k mod i 拆成 k - k / i * i，然后等差数列求和即可。
最后注意k/i可能会等于0，要特判一下
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
ll n, k;inline ll cal(ll l, ll r) { return (l + r) * (r - l + 1) / 2; }int main()
{scanf("%lld%lld", &n, &k);ll ans = n * k, sum = 0, l, r;for(int i = 1; i <= n; i = r + 1){l = i, r = k / i ? min(k / (k / i), n) : n;sum += (k / i) * cal(l, r);}printf("%lld\n", ans - sum);return 0;
}Hankson 的趣味题
看到x 和 b0的最小公倍数是 b1
那就枚举b1的因子作为x，然后看满不满足条件。
注意枚举因子的时候不要把完全平方数的因子算两遍
557ms
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }int main()
{int T;scanf("%d", &T);while(T--){int a0, a1, b0, b1;scanf("%d%d%d%d", &a0, &a1, &b0, &b1);int m = sqrt(b1 + 0.5), ans = 0;_for(x, 1, m)if(b1 % x == 0){if(lcm(x, b0) == b1 && gcd(x, a0) == a1) ans++;if(x != b1 / x){int tmp = b1 / x;if(lcm(tmp, b0) == b1 && gcd(tmp, a0) == a1) ans++;}}printf("%d\n", ans);}return 0;
}但是算法竞赛进阶指南上写枚举因子可以优化。
先打出素数表，然后质因数分解，然后用搜索组成因子
这种方法的确快了很多，196ms
注意质因数分解的时候注意可能最后有剩下一个大质数，要判断一下
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;const int MAXN = 1e5 + 10;
bool is_prime[MAXN];
vector<int> prime, ve;
int a[15], m, ans;
int a0, a1, b0, b1;void get_prime()
{memset(is_prime, true, sizeof(is_prime));is_prime[0] = is_prime[1] = false;REP(i, 2, MAXN){if(is_prime[i]) prime.push_back(i);REP(j, 0, prime.size()){if(i * prime[j] >= MAXN) break;is_prime[i * prime[j]] = false;if(i % prime[j] == 0) break;}}
}int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int lcm(int a, int b) { return a / gcd(a, b) * b; }inline bool check(int x)
{return lcm(x, b0) == b1 && gcd(x, a0) == a1;
}void deal()
{ve.clear();memset(a, 0, sizeof(a));m = 0;int t = b1;REP(j, 0, prime.size())if(t % prime[j] == 0){ve.push_back(prime[j]);while(t % prime[j] == 0){t /= prime[j];a[m]++;}m++;if(t == 1) break;}if(t > 1) {ve.push_back(t);a[m]++, m++;}
}void dfs(int i, int now) //i是第几个质因子
{if(i == m){if(check(now)) ans++;return;}int t;_for(j, 0, a[i]){if(j == 0) t = 1;else t *= ve[i];if((long long)t * now > b1) break;dfs(i + 1, now * t);}
}int main()
{get_prime();int T;scanf("%d", &T);while(T--){scanf("%d%d%d%d", &a0, &a1, &b0, &b1);deal();ans = 0;dfs(0, 1);printf("%d\n", ans);}return 0;
}X-factor Chain
我们拿100来看，100 = 2 x 2 x 5 x 5
那么很容易看出一个最长序列为
2 2 x 2 2 x 2 x 5 2 x 2 x 5 x 5
可以看出最长序列的长度为质因数的幂的和
那么一共有多少种呢？
上面的式子，我们可以只保留最后一个数
即2 2 5 5
这可以表示一种方案
我做的时候就卡在这里了，觉得可以用数学方法求出来，
但又不知道公式。
然后我就用搜索，然后超时。
后来看题解发现有公式。
有重复元素的排列方案：
设总元素个数为c，每个重复元素的数量为k1, k2, ……kn
那么答案就是c! / (k1! * k2!……kn!)
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef unsigned long long ull;
ull p[25];int main()
{p[0] = 1;_for(i, 1, 21) p[i] = p[i-1] * i;int x; while(~scanf("%d", &x)){int a[30], m = 0;int t = x, sum = 0;memset(a, 0, sizeof(a));_for(i, 2, t / i)if(t % i == 0){while(t % i == 0) {t /= i;a[m]++;sum++;}m++;if(t == 1) break;}if(t > 1) a[m]++, m++, sum++;ull ans = p[sum];REP(i, 0, m)ans /= p[a[i]]; printf("%d %llu\n", sum, ans);}return 0;
}[JLOI2014]聪明的燕姿
一开始就想到了公式，感觉可以搜索做，但不知道怎么个搜索方式。
想的是枚举n的因子，然后发现会很复杂。
但正解是反过来考虑，枚举质因子看n能不能被整除。
分两类。
（1）如果当前数很大，是一个质数与1的和就加入答案
（2）在根号当前数内枚举质数
#include<bits/stdc++.h>
#define REP(i, a, b) for(register int i = (a); i < (b); i++)
#define _for(i, a, b) for(register int i = (a); i <= (b); i++)
using namespace std;typedef long long ll;
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
bool is_prime[MAXN];
vector<int> prime, ans;
int n;void get_prime()
{memset(is_prime, true, sizeof(is_prime));is_prime[0] = is_prime[1] = false;REP(i, 2, MAXN){if(is_prime[i]) prime.push_back(i);REP(j, 0, prime.size()){if(i * prime[j] >= MAXN) break;is_prime[i * prime[j]] = false;if(i % prime[j] == 0) break;}}
}bool check(int x) //如果数非常大就可以用这种方法判断质数
{if(x < MAXN) return is_prime[x];REP(j, 0, prime.size()){if((long long)prime[j] * prime[j] > x) return true;if(x % prime[j] == 0) return false;}
}void dfs(int k, int now, int num)
{if(num == 1) { ans.push_back(now); return; }if((k == -1 || (num - 1) > prime[k]) && check(num - 1)) ans.push_back(now * (num - 1));REP(j, k + 1, prime.size()){int p = prime[j];if(p * p > num) break;for(int sum = p + 1, t = p; sum <= num; t *= p, sum += t)if(num % sum == 0)dfs(j, now * t, num / sum);}
}int main()
{get_prime();while(~scanf("%d", &n)){ans.clear();dfs(-1, 1, n);printf("%d\n", ans.size());sort(ans.begin(), ans.end());REP(i, 0, ans.size()) {printf("%d", ans[i]);printf("%s", i == ans.size() - 1 ? "\n" : " ");}}return 0;
}