2749: [HAOI2012]外星人

Time Limit:?3 Sec??Memory Limit:?128 MB
Submit:?568??Solved:?302
[Submit][Status][Discuss]

Description

Input

Output

輸出test行，每行一個整數(shù)，表示答案。

Sample Input

1
2
2 2
3 1

Sample Output

3

HINT

?

Test<=50 Pi<=10^5,1<=Q1<=10^9

?

Source

很好的一道題。

就是要求能phi出多少個2。。。

奇數(shù)時要加一(就是剛開始的時候變成偶數(shù)時要用一次。)

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define MAXN 100000 4 #define LL long long 5 int prime[10010],phi[MAXN+10],tot,f[MAXN+10]; 6 bool vis[MAXN+10]; 7 int read() 8 { 9 int s=0,fh=1;char ch=getchar(); 10 while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();} 11 while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();} 12 return s*fh; 13 } 14 void getEular() 15 { 16 int i,j; 17 phi[1]=1;tot=0; 18 for(i=2;i<=MAXN;i++) 19 { 20 if(vis[i]==false) 21 { 22 prime[++tot]=i; 23 phi[i]=i-1; 24 } 25 for(j=1;j<=tot&&prime[j]*i<=MAXN;j++) 26 { 27 vis[prime[j]*i]=true; 28 if(i%prime[j]==0) 29 { 30 phi[prime[j]*i]=prime[j]*phi[i]; 31 break; 32 } 33 phi[prime[j]*i]=phi[prime[j]]*phi[i]; 34 } 35 } 36 } 37 int main() 38 { 39 freopen("alien.in","r",stdin); 40 freopen("alien.out","w",stdout); 41 int T,i,m,p,q,n; 42 bool flag; 43 LL ans; 44 T=read(); 45 getEular(); 46 memset(f,0,sizeof(f));//f[i]代表i需要phi多少次才能化為1.(也就是等于能phi多少個2.) 47 f[1]=-1; 48 for(i=2;i<=MAXN;i++)f[i]=f[phi[i]]+1; 49 f[1]++;f[2]++; 50 while(T--) 51 { 52 m=read();ans=0; 53 flag=false;//判斷奇數(shù)時要加一. 54 for(i=1;i<=m;i++) 55 { 56 p=read();q=read(); 57 if(p==2)flag=true; 58 ans+=(LL)f[p]*q; 59 } 60 if(flag==false)ans++; 61 printf("%lld\n",ans); 62 } 63 fclose(stdin); 64 fclose(stdout); 65 return 0; 66 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/Var123/p/5296757.html

總結(jié)

以上是生活随笔為你收集整理的Bzoj 2749: [HAOI2012]外星人 欧拉函数,数论,线性筛的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。