AcWing 90. 64位整数乘法    原题链接    简单

作者： 作者的头像   不高兴的兽奶 ,  2022-09-22 21:47:29 ,  所有人可见 ,  阅读 325

0


莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路1：

分解b，让b个a相加

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

//龟速乘，计算res = a * b % p
LL qmul(LL a,LL b,LL p)
{
    LL res=0;
    while(b)
    {
        if(b&1) res=(res+a)%p;
        a=a*2%p;
        b>>=1;
    }
    return res;
}

int main()
{
    LL a,b,p;

    cin>>a>>b>>p;

    cout<<qmul(a,b,p)<<endl;

    return 0;
}

思路2：

利用__128int完成64位整数乘法, 3e38 < 2 ^ 128 < 4e38

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll a,b,p;

int main ()
{
    cin>>a>>b>>p;

    __int128 ap=a,bp=b,pp=p;

    ll ans=(ap*bp)%pp;

    cout<<ans<<endl;

    return 0;
}

4 评论

用户头像
WA声闹彻明   2022-09-23 09:25         踩      回复

这里还有种做法

用户头像
不高兴的兽奶   2022-09-23 09:35         踩      回复

确实，我感觉好神奇啊

用户头像
WA声闹彻明   2022-09-23 09:24         踩      回复 
#include<stdio.h>
#include<iostream>

#define ll long long
using namespace std;

int main()
{
    ll a,b,p;
    scanf("%lld%lld%lld",&a,&b,&p);
    //由a%p=a-(a/p)*p;
    //于是(a*b)%p=(a*b)-(a/b)/p*p;
    //if(a>=p || b>=p)不妨设a=k1*p+a1,b=k2*p+a2
    //(a*b)%p=(k1*k2*p*p+(k1*a2+k2*a1)*p+a1*a2)%p=(a1*a2)%p<p
    ll c=(long double)a*b/p;
    ll ans=a*b-c*p;

    printf("%lld\n",ans);
    return 0;
}
用户头像
不高兴的兽奶   2022-09-23 09:55         踩      回复

我也搞了种新做法，你可以看看

1024
x