【HAOI2012】外星人
又犯sb错了QAQ
原题：
艾莉欧在她的被子上发现了一个数字 ，她觉得只要找出最小的x使得，。
根据这个 她就能找到曾经绑架她的外星人的线索了。当然，她是不会去算，请你帮助她算出最小的x。
test<=50;pi<=10^5; 1<=qi<=10^9
恩看到phi一般都是要用到phi的积性的
根据样例解释可以看出来这个就是求连续求phi多少次能求出1
phi(a*b)=phi(a)*phi(b)
phi(phi(a*b))=phi(phi(a)*phi(b))=phi(phi(a))*phi(phi(b))
题目直接给的是质因子分解的形式，所以可以用f[i]表示i要phi几次变成1
显然如果f[prime_number]=f[prime_number-1]，f[prime_number*i]=f[prime_number]+f[i]
筛phi的时候搞一搞就行了
需要注意如果输入的数是奇数（即没有因子2）答案要+1
至于为什么……易证，请同学们自行推到（逃
这题又看题解了，然后又写了一个sb_bug，老是看题解+sb_bug，怎么办嘛QAQ
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #include<cmath> 6 using namespace std; 7 #define ll long long 8 int rd(){int z=0,mk=1; char ch=getchar(); 9 while(ch<'0'||ch>'9'){if(ch=='-')mk=-1; ch=getchar();} 10 while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0'; ch=getchar();} 11 return z*mk; 12 } 13 int n; 14 int f[110000]; 15 bool flg[110000]; 16 int phi[110000],prm[110000],tt=0; 17 void gtphi(){ 18 n=100000; 19 memset(flg,0,sizeof(flg)); 20 phi[1]=f[1]=1; 21 for(int i=2;i<=n;++i){ 22 if(!flg[i]){ phi[i]=i-1,f[i]=f[i-1]; prm[++tt]=i;} 23 for(int j=1;j<=tt && i*prm[j]<=n;++j){ 24 flg[i*prm[j]]=true; 25 f[i*prm[j]]=f[i]+f[prm[j]]; 26 if(!(i%prm[j])){ phi[i*prm[j]]=phi[i]*prm[j]; break;} 27 phi[i*prm[j]]=phi[i]*phi[prm[j]]; 28 } 29 } 30 } 31 int main(){//freopen("ddd.in","r",stdin); 32 gtphi(); 33 int T; cin>>T; while(T--){ 34 cin>>n; 35 int l,r; ll bwl=0; bool flg=1; 36 while(n--){ 37 l=rd(),r=rd(); 38 bwl+=(ll)f[l]*r; 39 if(l==2) flg=0; 40 } 41 printf("%I64d ",bwl+flg); 42 } 43 return 0; 44 }