首页 > ACM题库 > HDU-杭电 > HDU 1420 Prepared for New Acmer-数论-[解题报告] C++
2013
12-10

HDU 1420 Prepared for New Acmer-数论-[解题报告] C++

Prepared for New Acmer

问题描述 :

集训进行了将近2个礼拜,这段时间以恢复性训练为主,我一直在密切关注大家的训练情况,目前为止,对大家的表现相当满意,首先是绝大部分队员的训练积极性很高,其次,都很遵守集训纪律,最后,老队员也起到了很好的带头作用,这里特别感谢为这次DP专题练习赛提供题目和测试数据的集训队队长xhd同学.

特别高兴的是,跟随集训队训练的一批新队员表现非常好,进步也比较显著,特别是训练态度大大超出我的预期,我敢说,如果各位能如此坚持下去,绝对前途无量!

考虑到新队员还没有经过系统训练,我这里特别添加一道简单题:
给定三个正整数A,B和C(A,B,C<=1000000),求A^B mod C的结果.

希望各位都能体会到比赛中AC的快乐,绝对的量身定制,很高的待遇哟,呵呵…

输入:

输入数据首先包含一个正整数N,表示测试实例的个数,然后是N行数据,每行包括三个正整数A,B,C。

输出:

对每个测试实例请输出计算后的结果,每个实例的输出占一行。

样例输入:

3
2 3 4
3 3 5
4 4 6

样例输出:

0
2
4

Prepared for New Acmer

蒙哥马利幂模思想:

 在幂模运算中,通常是用幂模运算转换为乘模运算。有以下两个公式:

1)a*b%n=a%n)*(b%n)%n

2)(a+b%n=a%n+b%n)%n

当我们计算D=C^15%N时,有:

C1=C*C%N=C^2%N

C2=C1*C%N=C^3%N

C3=C2*C2%N=C^6%N

C4=C3*C%N=C^7%N

C5=C4*C4%N=C^14%N

C6=C5*C%N=C^15%N

所以,幂模运算可以转化为乘模运算。继续看,我们会发现,要求D=C^E%N,要知道E何时能整除2,并不需要反复进行减一或者除二的操作,只需要验证E的二进制个位是0还是1就行了。

本题代码:

#include <cstdio>

__int64 fun(__int64 A,__int64 B,__int64 C)
{
	__int64 k = 1;
	 A%=C;
	while(B>=1)
	{
		if((B&1)!=0)
			k = (k*A)%C;
        B>>= 1;
		A = A*A%C;
	}
	return k;
}
int main(int argc, char *argv[])
{
	int n;
	scanf("%d",&n);
	__int64 A,B,C;
	while(n--)
	{
		scanf("%I64d%I64d%I64d",&A,&B,&C);
		printf("%I64d\n",fun(A,B,C));
	}
	return 0;
}
普通代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
#include <iomanip>

using namespace std;
int main(int argc, char *argv[])
{
    int n;
    scanf("%d",&n);
    int A,B,C;
    while(n--)
    {
        scanf("%d%d%d",&A,&B,&C);
        __int64 ans = 1;
        for(int i = 1; i <= B; i++)
        {
            ans*=A;
            ans%=C;   //注意要求余,不然很容易数据溢出;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/i_fuqiang/article/details/8701483


  1. /*
    * =====================================================================================
    *
    * Filename: 1366.cc
    *
    * Description:
    *
    * Version: 1.0
    * Created: 2014年01月06日 14时52分14秒
    * Revision: none
    * Compiler: gcc
    *
    * Author: Wenxian Ni (Hello World~), [email protected]
    * Organization: AMS/ICT
    *
    * =====================================================================================
    */

    #include
    #include

    using namespace std;

    int main()
    {
    stack st;
    int n,i,j;
    int test;
    int a[100001];
    int b[100001];
    while(cin>>n)
    {
    for(i=1;i>a[i];
    for(i=1;i>b[i];
    //st.clear();
    while(!st.empty())
    st.pop();
    i = 1;
    j = 1;

    while(in)
    break;
    }
    while(!st.empty()&&st.top()==b[j])
    {
    st.pop();
    j++;
    }
    }
    if(st.empty())
    cout<<"YES"<<endl;
    else
    cout<<"NO"<<endl;
    }
    return 0;
    }

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。