首页 > 代码库 > BZOJ2749 [HAOI2012]外星人
BZOJ2749 [HAOI2012]外星人
数论好题！！！
首先由题目给的公式，对于素数x > 2，phi(x)会变出好多2...而phi(2) = 1
YY一下就可以发现，就是求出每一个质数经过分解会变出多少个2来，2的个数就是ans。
于是我们令f[i]表示i分解出了几个2：这一过程类似素数筛法
i为质数，f[i] = f[i - 1]；否则，f[i * prime[j] = f[i] + f[prime[j]] （<--这就是传说中的纯O(n)线性筛）
另：如果一开始n为奇数，则ans需+ 1，因为变出2需要第一步。
1 /************************************************************** 2 Problem: 2749 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:256 ms 7 Memory:1704 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13 14 using namespace std;15 typedef long long LL;16 const int Maxn = 100005;17 LL f[Maxn + 10], ans, del;18 int T, P, Q, m, p[5000], cnt;19 bool x[Maxn + 10];20 21 void pre_work(){22 int t;23 f[1] = 1;24 for (int i = 2; i <= Maxn; ++i){25 if (!x[i])26 p[++cnt] = i, f[i] = f[i - 1];27 for (int j = 1; j <= cnt && i * p[j] <= Maxn; ++j){28 t = i * p[j];29 x[t] = 1;30 f[t] = f[i] + f[p[j]];31 if (!(i % p[j])) break;32 }33 }34 }35 36 int main(){ 37 scanf("%d", &T);38 pre_work();39 while (T--){40 scanf("%d", &m);41 ans = 0, del = 1;42 for (int i = 1; i <= m; ++i){43 scanf("%d%d", &P, &Q);44 if (P == 2) del = 0;45 ans += f[P] * Q;46 }47 printf("%lld\n", ans + del);48 }49 return 0;50 }
BZOJ2749 [HAOI2012]外星人
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。