| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
写个慢点但不取巧的办法...后六位什么的
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
int t2[10001],t5[10001],te[10001];
int quickpow(int a,int b,int c){
if (b==0) return 1;
else if (b==1) return a%c;
else return quickpow(a,b/2,c)*quickpow(a,b-b/2,c)%c;
}
void gen(){
int i,j,k;
for (i=1;i<=10000;i++){
if (i%2) t2[i]=t2[i-1];
else{
for (k=2,j=4;j<=i && i%j==0;k++,j*=2);
t2[i]=t2[i-1]+k-1;
}
}
for (i=1;i<=10000;i++){
if (i%5) t5[i]=t5[i-1];
else{
for (k=2,j=25;j<=i && i%j==0;k++,j*=5);
t5[i]=t5[i-1]+k-1;
}
}
te[1]=1;
for (i=2;i<=10000;i++){
int j=i;
while (j%2==0)j/=2;
while (j%5==0)j/=5;
te[i]=te[i-1]*j%10;
}
}
int main()
{
int n;
gen();
while (cin>>n){
cout.width(5);
int ans=te[n]*quickpow(2,t2[n]-t5[n],10)%10;
cout<<right<<n<<" -> "<<ans<<endl;
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator