題目：Just the Facts

思路：枚舉10000素?cái)?shù)內(nèi)，各因子出現(xiàn)的次數(shù)，然后取模為10。因?yàn)?是由2和5構(gòu)成的，所以2和5的冪單獨(dú)討論，同時由于2的冪肯定大于5的，所以我們最后要算的再乘上2的減去后的冪就可以得到。

?

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=10001;
int n_prime=0;
int prime[maxn];
int vis[maxn];
void Prime()
{memset(vis,1,sizeof(vis));vis[0]=vis[1]=0;for(int i=2;i<maxn;i++)if(vis[i]){prime[++n_prime]=i;for(int j=2*i;j<maxn;j+=i)vis[j]=0;}
}
int get(int n,int p)
{int ans=0;int tmp=p;while(n>=tmp){ans+=n/tmp;tmp*=p;}return ans;
}
long long Pow(long long a,long long b)
{long long ans=1;while(b){if(b&1){b--;ans=(ans*a)%10;}else{b/=2;a=(a*a)%10;}}return ans;
}
int main()
{Prime();int n;while(scanf("%d",&n)!=EOF){long long ans=1;for(int i=1;i<=n_prime;i++){if(prime[i]==5||prime[i]==2)continue;ans=(ans*Pow(prime[i],get(n,prime[i])))%10;}ans=(ans*Pow(2,get(n,2)-get(n,5)))%10;printf("%5d -> %lld\n",n,ans);}return 0;
}

View Code

?

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

總結(jié)

以上是生活随笔為你收集整理的virtual hust 2013.6.20 数论基础题目 D - Just the Facts的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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