【HAOI2012】外星人

Source and Judge

HAOI2012
bzoj2749
luogu2350

Record

2h

Analysis

请先思考后再展开

题面上的x是指函数的阶,可以理解为嵌套数量

首先,phi有个奇妙的性质:只有phi(2)=1,其他的结果都是偶数
这个不难证明,根据欧拉函数的公式,除2以外的素数都是奇数,减一得到偶数

逆向考虑一下,那么为了得到1,迟早要变成2的形式
对于a为偶数的情况,枚举拆phi会去除一个2,然后2-1在连乘中没有影响,所以等价于一个2去除了
但此时其他的素数会变成p-1,一定会产生2(如果有)

因为这个性质中,2的去除每次拆开只会进行一次(整个a而言,而不是每个素数都这样)
那么这个2的次数其实能推导出嵌套深度,所以问题转化为,求出N在不断拆开的过程中,产生的2的数量

而对于a是奇数的情况,这一次拆开不会消除2,所以应该在原本的基础上+1
同时不需要考虑以后的情况,就像上文所说的,以后的phi的结果都是偶数

$f(prime)=f(prime-1)$
$f(prime^k)=f(prime)*k$
$f(num)=\sum f(prime^k)$
这个是可以线筛的时候顺便搞的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
//Zory-2018
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
namespace mine
{
const int INF=0x3f3f3f3f;
typedef long long ll;
const int MAX_NUM=100001;
int pr=0,prime[MAX_NUM];
bool isp[MAX_NUM];
int f[MAX_NUM];
void pre()
{
memset(isp,1,sizeof isp);
for(int i=2;i<MAX_NUM;i++)
{
if(isp[i]) prime[++pr]=i,f[i]=(i==2?1:f[i-1]);
for(int j=1;j<=pr and (ll)i*prime[j]<MAX_NUM;j++)
{
isp[i*prime[j]]=0;
f[i*prime[j]]=f[i]+f[prime[j]];
if(i%prime[j]==0) break;
}
}
}
void main()
{
pre();
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
ll ans=0;bool two=0;
for(int i=1;i<=n;i++)
{
int p,k;scanf("%d%d",&p,&k);
ans+=(ll)f[p]*k;if(p==2) two=1;
}
if(!two) ans++;
printf("%lld\n",ans);
}
}
}
int main()
{
mine::main();
}

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/f69a.html
转载请注明出处,谢谢!