poj 2689
要对数据敏感，L和R很大，但是L-R很小。
可以在（R - L）loglogR的时间内用筛法筛出所有质数。
然后扫一遍就好了。
有些细节要注意，有些地方会爆int，0和1不能算进去。
#include<cstdio>
#include<cstring>
#include<vector>
#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 MAXM = 1e6 + 10;
bool is_prime[MAXM];
vector<int> prime;
ll L, R;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;}}
}void work()
{memset(is_prime, true, sizeof(is_prime));REP(j, 0, prime.size()){int p = prime[j];int i = (L + p - 1) / p;if(i == 1) i++;for(ll k = (ll)i * p; k <= R; k += p)is_prime[k - L] = false;}
}int main()
{get_prime();while(~scanf("%lld%lld", &L, &R)){work();int l1, r1, ans1 = 1e9, l2, r2, ans2 = 0;vector<int> ve;_for(i, 0, R - L)if(i + L >= 2 && is_prime[i])ve.push_back(i + L);if(ve.size() <= 1) puts("There are no adjacent primes.");else{REP(i, 1, ve.size()){int d = ve[i] - ve[i - 1];if(d < ans1){ans1 = d;l1 = ve[i - 1];r1 = ve[i];}if(d > ans2){ans2 = d;l2 = ve[i - 1];r2 = ve[i];}}printf("%d,%d are closest, %d,%d are most distant.\n", l1, r1, l2, r2);}}return 0;
}bzoj 1607
用类似筛法的思想，每个数把它所有的倍数的答案都加1
可能有相同的数，所以要优化，可以预处理一下。
#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 = 1e6 + 10;
int a[MAXN], b[MAXN];
int c[MAXN], num[MAXN], ans[MAXN], m, n;int main()
{scanf("%d", &n);REP(i, 0, n){scanf("%d", &a[i]);b[i] = a[i];}int t = 1;sort(b, b + n);REP(i, 0, n){if(i > 0 && b[i] == b[i - 1]) num[m-1]++;else num[m] = 1, c[m++] = b[i];}REP(i, 0, m) ans[c[i]] = num[i] - 1;REP(i, 0, m){int t = c[i];for(int j = 2; j * t <= c[m - 1]; j++)ans[j * t] += num[i];}REP(i, 0, n) printf("%d\n", ans[a[i]]);return 0;
}「一本通 6.2 练习 1」质因数分解
超级大水题
#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;
bool is_prime[MAXN];
vector<int> prime;
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;}}
}int main()
{get_prime();scanf("%d", &n);REP(j, 0, prime.size())if(n % prime[j] == 0){printf("%d\n", n / prime[j]);break;}return 0;
}「一本通 6.2 练习 3」Goldbach's Conjecture
水水水
#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 = 1e6 + 10;
bool is_prime[MAXN];
vector<int> prime;
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;}}
}int main()
{get_prime();while(~scanf("%d", &n) && n){bool ok = false;REP(j, 1, prime.size())if(is_prime[n - prime[j]]){printf("%d = %d + %d\n", n, prime[j], n - prime[j]);ok = true;break;}if(!ok) puts("Goldbach's conjecture is wrong.");}return 0;
}「一本通 6.2 练习 4」Sherlock and His Girlfriend
一开始写的非常麻烦
#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;
int n, ok;inline bool check(int k) { return 2 <= k && k <= n + 1; }void get_prime()
{memset(is_prime, true, sizeof(is_prime));is_prime[0] = is_prime[1] = false;REP(i, 2, n + 1){if(is_prime[i]) prime.push_back(i);REP(j, 0, prime.size()){if(i * prime[j] > n + 1) break;is_prime[i * prime[j]] = false;if(check(i) && check(i * prime[j])) ok = 1;if(i % prime[j] == 0) break;}}
}int main()
{scanf("%d", &n);get_prime();if(ok) printf("2\n");else printf("1\n");_for(i, 2, n + 1){if(is_prime[i]) printf("1");else if(ok) printf("2");printf("%s", i == n + 1 ? "\n" : " ");}return 0;
}后来发现不用线性筛法代码会减少很多。并且只要n>2就输出颜色最少是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;const int MAXN = 1e5 + 10;
int s[MAXN], n;int main()
{scanf("%d", &n);if(n > 2) printf("2\n");else printf("1\n");_for(i, 2, n + 1)if(!s[i])for(int j = i * 2; j <= n + 1; j += i) s[j] = 1;_for(i, 2, n + 1){if(!s[i]) printf("1 ");else printf("2 ");}return 0;
}bzoj 2721
这道题我想了好久还是不会。
看题解的时候感觉特牛逼。
到底是怎么想到把y！转化成n！+t的
？？？？？
因为y > n!，所以设y = n！+t
代入可以求得
x = （n！）^2 / t +n!
所以答案就是n！的因子个数。
这个转化真的很秀。
那么怎么求呢？
首先因子个数为(c1 + 1)(c2+1)……(cn+1),c为质因数的幂
那么问题转化为怎么求质因数的幂
对于n！，质因数p的幂为n！ / p + n！ / ( p*p) +n！ / (p*p*p)
很好理解，把p的倍数的因子都有p，然后平方有两个，所以应该加上平方的，立方有三个……
代码是这样
ll cnt = 0;while(t){cnt += t / prime[j];t /= prime[j];}然后呢，因为是n！的平方，所以每个因子的个数要乘以2.代入得
答案为（2*cnt1 + 1） * (2 * cnt2 + 1)……
这道题就解决了。
#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 = 1e6 + 10;
const int MOD = 1e9 + 7;
bool is_prime[MAXN];
vector<int> prime;
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;}}
}int main()
{get_prime();scanf("%d", &n);ll ans = 1;REP(j, 0, prime.size()){int t = n;ll cnt = 0;while(t){cnt += t / prime[j];t /= prime[j];}ans = ans * (cnt << 1 | 1) % MOD;}printf("%lld\n", ans);return 0;
}