首页 > 代码库 > NYOJ 676 小明的求助

NYOJ 676 小明的求助

小明的求助

时间限制:2000 ms  |  内存限制:65535 KB
难度:2
描述
小明对数学很有兴趣,今天老师出了道作业题,让他求整数N的后M位,他瞬间感觉老师在作弄他,因为这是so easy! 当他看到第二道题目的时候,他就确定老师在捉弄他了,求出N^P的后M位,因为他不会了。你能帮他吗?
输入
第一行包含一个整数T(T <= 1000),代表测试数据组数。
接下来的T行每行含三个整数,N,P,M(1 <= N <= 10^10,1 <= P <= 10^15,1 <= M <= 9)。
输出
输出格式“Case #i: ans”(不含引号),i表示第i组测试数据,ans为所求结果。
样例输入
2
2 4 1
3 7 2
样例输出
Case #1: 6
Case #2: 87
快速幂模!
AC码:
#include<stdio.h>
long long n,p,m;
long long Mi(long long mm)
{
	long long a=n,b=p,result=1;
	while(b)
	{
		if(b&1)
			result=(result*a)%mm;
		a=(a*a)%mm;
		b=b/2;
	}
	return result%mm;
}
int main()
{
	long long T,i,mm;
	int count=1;
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld%lld%lld",&n,&p,&m);
		mm=1;
		for(i=1;i<=m;i++)
			mm*=10;
		printf("Case #%d: %lld\n",count++,Mi(mm));
	}
	return 0;
}

二分法!
AC码:
#include<stdio.h>
long long fun(long long n,long long p,long long mm)
{
	long long result;
	if(p==1)
		return n;
	result=fun(n,p/2,mm);
	if(p%2==1)
		return (((result*result)%mm)*n)%mm;
	else
		return (result*result)%mm;
}
int main()
{
	int T,i,j;
	long long n,p,m,mm;
	scanf("%lld",&T);
	for(i=1;i<=T;i++)
	{
		scanf("%lld%lld%lld",&n,&p,&m);
		mm=1;
		for(j=1;j<=m;j++)
			mm*=10;
		printf("Case #%d: %lld\n",i,fun(n,p,mm));
	}
	return 0;
}