文章

9

粉丝

0

获赞

46

访问

904

头像
幂次方 题解:C语言快速幂
P1017 贵州大学机试题
发布于2026年3月13日 22:03
阅读数 142

#include<stdio.h>
#define mod 233333//定义模数大小
typedef long long ll;//重命名long long为ll
ll ksm(ll x,ll y,ll p)//快速幂公式,(a*b)%m=(a%b*b%b)%b,可类比加减法
{
    int res=1;//初始化结果
    x=x%p;//先处理底数,防止太大,结果是一样的
    while(y!=0)//指数可以看为二进制,为2^n加在一块的,二进制位相加
    {
        if(y%2==1)//只要二进制位有效,就进行操作
        {
            res=res*x%p;//相当于结果与此时的二进制位相乘然后取模,循环找有效位操作
        }
        x=x*x%p;//相当于每次对x进行翻倍操作,相当于对底数进行二进制的翻倍,如初始x=2,则x*x=4,接着x*x=4*4=16,相当于翻倍
        y/=2;//相当于把指数右移一位,为了寻找有效位
    }
    return res;//返回最终结果
}            
int main()
{
    ll x,n;
    scanf("%ld %ld",&x,&n);
    printf...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发