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
", 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
", 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
", 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
", 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
", 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
", ans.size());
sort(ans.begin(), ans.end());
REP(i, 0, ans.size())
{
printf("%d", ans[i]);
printf("%s", i == ans.size() - 1 ? "
" : " ");
}
}
return 0;
}