kuangbin专题十四 数论基础 LightOJ 1282

本文主要是介绍kuangbin专题十四 数论基础 LightOJ 1282，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：
给定两个数n,k 求n^k的前三位和最后三位。
题解：
后面三位可以用快速幂求，难就难在前面的三位怎么做了，看了很多，发现有个大佬用除法去求出前三位，ORZ，有个坑点就是后三位记得补零，和如果你是用除法去求前面三位的记得用double去做，因为你如果用long long int 去做的话，除的时候会去掉小数部分的，会导致后面的数无法进位的。然后再你返回double值的时候可以有两种操作，一是再返回double值的时候-0.5，二是直接再输出的时候强制转换成long long int。
其实第二种方法我感觉才是这道题真正想你去做的方法，作为一个数论只会GCD的家伙，还是推荐你们去看一下这位dalao的博客好点，毕竟人家说的比我好，我就没必要让你们看我的半知半解的解说了。http://blog.csdn.net/gscsdlz/article/details/51886094
第一种方法

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long int
const int mod=1000;
double q_pow1(double a,LL n)
{double ans=1;while(n>0){if(n&1)ans=(ans*a);n/=2;a=(a*a);while(ans>=mod)ans/=10;while(a>=mod)a/=10;}return ans;
}
LL q_pow2(LL a,LL n)
{LL ans=1;a%=mod;while(n>0){if(n&1)ans=(ans*a)%mod;n/=2;a=(a*a)%mod;} return ans;
}
int main()
{int t,k=1;scanf("%d",&t);while(t--){LL a,n;scanf("%lld%dlld",&a,&n);printf("Case %d: %lld %03lld\n",k++,(LL)q_pow1(a,n),q_pow2(a,n));}
} 
/*
下面这种输出也是可以的
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define LL long long int
const int mod=1000;
double q_pow1(double a,LL n)
{double ans=1;while(n>0){if(n&1)ans=(ans*a);n/=2;a=(a*a);while(ans>=mod)ans/=10;while(a>=mod)a/=10;}return (ans-0.5);
}
LL q_pow2(LL a,LL n)
{LL ans=1;a%=mod;while(n>0){if(n&1)ans=(ans*a)%mod;n/=2;a=(a*a)%mod;} return ans;
}
int main()
{int t,k=1;scanf("%d",&t);while(t--){LL a,n;scanf("%lld%dlld",&a,&n);printf("Case %d: %.0lf %03lld\n",k++,q_pow1(a,n),q_pow2(a,n));}
} 
*/ 

第二种方法

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define LL long long int
const int mod=1000;
LL q_pow(LL a,LL n)
{LL ans=1;a%=mod;while(n>0){if(n&1)ans=(ans*a)%mod;n/=2;a=(a*a)%mod;} return ans;
}
int main()
{int t,k=1;scanf("%d",&t);while(t--){LL a,n;scanf("%lld%dlld",&a,&n);int res=pow(10,2.0+fmod((double)n*log10((double)a),1));printf("Case %d: %lld %03lld\n",k++,res,q_pow(a,n));}
} 
//fmod是求x/y的余数的，那么fmod(x,1)就可以得出x的小数部分了，Orz突然感觉我还有很多很多好的函数都不会啊 

这篇关于kuangbin专题十四 数论基础 LightOJ 1282的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---