AcWing 90. 64位整数乘法(O(1)快速乘)

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 90. 64位整数乘法(O(1)快速乘) 原题链接简单

作者：

这个显卡不太冷 , 2019-04-10 13:35:44 , 所有人可见 , 阅读 3978

10

9

神奇O(1)快速乘

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll ksc(ll x,ll y,ll mod)
{
    return (x*y-(ll)((long double)x/mod*y)*mod+mod)%mod;     
}
int main()
{
    ll a, b, p;
    cin >> a >> b >> p;
    cout << ksc(a, b, p);
}

20 评论

C++大蒟蒻 2022-10-14 12:38

看不懂的可以看这里

玖六 2022-04-06 18:35

(xy-(ll)((long double)x/mody)*mod+mod)%mod; 没看懂（我不过是个数学小垃圾QAQ）

Conan15 2022-02-27 09:01

大神这是啥意思啊

Anohkx 2023-10-02 23:35

蓝书上的法2

林小胖 2021-07-18 12:02

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,p;
inline ll binmul(ll a, ll b, ll m)
{
    unsigned long long c =(unsigned long long)a * b - (unsigned)((long double)a / m * b + 0.5L) * m;
    if (c < m)return c;
    return c + m;
}
int main()
{
    cin>>a>>b>>p;
    cout<<binmul(a,b,p)<<endl;
    return 0;
}

为什么这个不行呀错在哪里

芝士梁增 26天前

有测试集直接把ab的计算结果直接吞掉了，当ab恰好是一个正好能够比long long的范围大1的时候，a*b算出来是零。可以尝试代码

#include<iostream>
using namespace std;

typedef unsigned long long ULL;

ULL ANS(ULL a,ULL b,ULL p){

    a%=p;b%=p;
    ULL c = (long double)a*b/p;
    //cout<<a<<b<<endl;
    ULL x = a*b-p,y = c*p-p;
    //cout<<x<<" "<<y<<endl;
    long long ans = (long long)(x%p) - (long long)(y%p);

    if(ans<0) ans+=p;
    return ans;
}

int main(){
    ULL a,b,p;
    scanf("%llu%llu%llu",&a,&b,&p);

    cout<<ANS(a,b,p)<<endl;
    return 0;

}

芝士梁增 26天前回复了芝士梁增的评论

亲测能过（

可比百分 2021-03-16 23:40

我想问的是，a*b没爆的话，为啥还要用模的定义，直接mod p不行吗

此账号已注消 2021-03-12 15:58

x*y不会溢出吗

Neal_lee 2020-04-02 18:30

似乎有一点问题？
对于输入：
12312312312312312 45645645645645645 3
三个数都小于1e18，但是程序输出是1,
而两个乘数都是3的倍数，错了

Neal_lee 2020-04-02 18:34

我还是乖乖用__int128吧

这个显卡不太冷 2020-04-03 16:26

可以先把x和y都对mod取模

林小胖 2021-07-18 11:59 回复了 Neal_lee 的评论

__int128 怎么用呀兄弟

林小胖 2021-07-18 12:01 回复了 Neal_lee 的评论

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,p;
inline ll binmul(ll a, ll b, ll m)
{
    unsigned long long c =(unsigned long long)a * b - (unsigned)((long double)a / m * b + 0.5L) * m;
    if (c < m)return c;
    return c + m;
}
int main()
{
    cin>>a>>b>>p;
    cout<<binmul(a,b,p)<<endl;
    return 0;
}

我在OIwiki上看到的过不了