题目：输入x,n，范围（x<1000,n<1e18）输出x的n次方除1e9+7的余数
x,n很大的时候也要能输出答案 注意效率
代码：
#include"iostream"
#define K 1000000007
using namespace std;
int main()
{
    int x,n,i,ans;
    cin>>x;
    cin>>n;
    ans=x%K;
    for (i=0;i<n-1 ;i++ )
        ans=(ans*x)%K;
    cout<<ans;
    return 0;
}

n是int型，恐怕会溢出

记得处理长整形数据后可以用二分法或者理解成二进制的01位运算实现~

((a∧b)∧2)%c=(((a∧b)%c)∧2)%c
这个是我自己理解的~或者网上可以搜到这个思想的解法~记得是快速求余的方法么……一时不知道那个术语怎么表达了~

[此贴子已经被作者于2017-10-10 23:45编辑过]

深夜断网……于是用手机临时用C敲一个……对着电脑测试了一下~看看有没有问题~

#include<stdio.h>

unsigned int  fun(unsigned int x,unsigned int n,unsigned int k);

int main()
{
    unsigned int x=0;
    unsigned int n=0;
    unsigned int k=0;
    
    scanf("%u%u%u",&x,&n,&k);

    printf("%u\n",fun(x,n,k));

    return 0;

}


unsigned int  fun(unsigned int x,unsigned int n,unsigned int k)
{
    unsigned int s=1;
    unsigned int t=x%k;

    while (n)
    {
         if (n%2)
             s=s*t%k;

        t=t*t%k;
        n>>=1;
    }

    return s;
}

[此贴子已经被作者于2017-10-11 03:17编辑过]

先分析一下
如果是依次相乘，因为结果是除1000000007的余数，那么中间结果最大可能出现 1000000006 * 999，需要40bits存储
如果是用快速幂，因为结果是除1000000007的余数，那么中间结果最大可能出现 1000000006 * 1000000006，需要60bits存储
所以这题的数据类型得用 uint64_t/int64_t
另外，既然题目中提到“余数”，那就不考虑x为负或n为负的情况。

#include <stdio.h>
#include <inttypes.h>

#define K 1000000007

int main(void)
{
    uint32_t x, n;
    scanf( "%"SCNu32"%"SCNu32, &x, &n );
   
    uint32_t r = 1;
    for( uint64_t t=x; n!=0; n>>=1, t=t*t%K )
        if( n%2 == 1 )
            r = (r*t)%K;

    printf( "%"PRIu32"\n", r );
    return 0;
}

收到的鲜花

• 九转星河 于 2017-10-11 10:13 送鲜花  20朵   附言：厉害~学习了~

这个是好久远的题了哈哈，蟹蟹大家帮助呀。当时只是想了最简单的方法，没有深入了解，回来之后发现大家的思路都很棒，十分感谢十分感谢~~~