0x01位运算——64位整数乘法

问题简析

C++内置的最高整数类型是64位，所以显然不能通过直接运算得到答案，我们需要一些特殊的处理方法，在这里提供两种方法。

思路一

类似于快速幂的思想，把b拆分成k位二进制。
b = C k − 1 ∗ 2 k − 1 + C k − 2 ∗ 2 k − 2 . . . + C 0 ∗ 2 0 。 b=C_{k-1}*2^{k-1}+C_{k-2}*2^{k-2}...+C_{0}*2^{0}。 b=Ck−1​∗2k−1+Ck−2​∗2k−2...+C0​∗20。
a ∗ b = C k − 1 ∗ 2 k − 1 ∗ a + C k − 2 ∗ 2 k − 2 ∗ a . . . + C 0 ∗ 2 0 ∗ a 。 a*b=C_{k-1}*2^{k-1}*a+C_{k-2}*2^{k-2}*a...+C_{0}*2^{0}*a。 a∗b=Ck−1​∗2k−1∗a+Ck−2​∗2k−2∗a...+C0​∗20∗a。
若 算 出 a ∗ b i − 1 m o d   p ， 则 计 算 ( a ∗ b i − 1 ) ∗ 2 m o d   p 的 过 程 中 不 会 超 过 2 ∗ 1 0 18 ， l o n g   l o n g 可 以 胜 任 。 若算出a*b^{i-1}mod~p，则计算(a*b^{i-1})*2mod~p的过程中不会超过2*10^{18}，long ~long可以胜任。 若算出a∗bi−1mod p，则计算(a∗bi−1)∗2mod p的过程中不会超过2∗1018，long long可以胜任。

时间复杂度分析

分 解 出 的 项 数 为 k = ⌈ l o g 2 ( b + 1 ) ⌉ 分解出的项数为k=left lceil log_{2}(b+1) right rceil 分解出的项数为k=⌈log2​(b+1)⌉
时 间 复 杂 度 : O l o g 2 ( n ) 时间复杂度:O log_{2}(n) 时间复杂度:Olog2​(n)

代码实现

#include

typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5+10,M = N,INF = 0x3f3f3f3f,P = 998244353;


int main()
{
    std::ios::sync_with_stdio(false);
    ll a,b,p;
    std::cin>>a>>b>>p;
    ll res = 0;
    for(; b ; b >>= 1)
    {
        if(b&1)res = (res + a)%p;
        a = a * 2 % p;
    }
    std::cout< 
思路二
 
 
 

     
      
       
        
         利
        
        
         用
        
        
         a
        
        
         ∗
        
        
         b
        
        
          
        
        
         m
        
        
         o
        
        
         d
        
        
          
        
        
         p
        
        
         =
        
        
         a
        
        
         ∗
        
        
         b
        
        
         −
        
        
         
          ⌊
         
         
          a
         
         
          ∗
         
         
          b
         
         
          /
         
         
          p
         
         
          ⌋
         
        
        
         ∗
        
        
         p
        
        
         ，
        
        
         
          ⌊
         
         
          ⌋
         
        
        
         为
        
        
         向
        
        
         下
        
        
         取
        
        
         整
        
       
       
        利用a*b ~mod~p=a*b-left lfloor a*b/p right rfloor*p，left lfloor right rfloor为向下取整
       
      
     利用a∗b mod p=a∗b−⌊a∗b/p⌋∗p，⌊⌋为向下取整
 
     
      
       
        
         首
        
        
         先
        
        
         ，
        
        
         假
        
        
         设
        
        
         a
        
        
         <
        
        
         p
        
        
         ,
        
        
         b
        
        
         <
        
        
         p
        
        
         ,
        
        
         那
        
        
         么
        
        
         a
        
        
         ∗
        
        
         b
        
        
         /
        
        
         p
        
        
         下
        
        
         取
        
        
         整
        
        
         之
        
        
         后
        
        
         一
        
        
         定
        
        
         也
        
        
         小
        
        
         于
        
        
         p
        
        
         ，
        
        
         我
        
        
         们
        
        
         可
        
        
         以
        
        
         使
        
        
         用
        
        
         浮
        
        
         点
        
        
         数
        
        
         完
        
        
         成
        
        
         中
        
        
         间
        
        
         计
        
        
         算
        
        
         。
        
       
       
        首先，假设a 
     
      
       
        
         l
        
        
         o
        
        
         n
        
        
         g
        
        
          
        
        
         d
        
        
         o
        
        
         u
        
        
         b
        
        
         l
        
        
         e
        
        
         的
        
        
         浮
        
        
         点
        
        
         数
        
        
         有
        
        
         效
        
        
         数
        
        
         字
        
        
         在
        
        
         18
        
       
       
        long~double的浮点数有效数字在18
       
      
     long double的浮点数有效数字在18~
     
      
       
        
         19
        
        
         位
        
        
         之
        
        
         间
        
        
         ，
        
        
         可
        
        
         以
        
        
         胜
        
        
         任
        
        
         。
        
       
       
        19位之间，可以胜任。
       
      
     19位之间，可以胜任。
 
     
      
       
        
         a
        
        
         ∗
        
        
         b
        
        
         和
        
        
         
          ⌊
         
         
          a
         
         
          ∗
         
         
          b
         
         
          /
         
         
          p
         
         
          ⌋
         
        
        
         ∗
        
        
         p
        
        
         可
        
        
         能
        
        
         会
        
        
         很
        
        
         大
        
        
         ,
        
        
         但
        
        
         是
        
        
         易
        
        
         知
        
        
         它
        
        
         们
        
        
         的
        
        
         差
        
        
         值
        
        
         一
        
        
         定
        
        
         在
        
        
         0
        
       
       
        a*b 和left lfloor a*b/p right rfloor*p可能会很大,但是易知它们的差值一定在0
       
      
     a∗b和⌊a∗b/p⌋∗p可能会很大,但是易知它们的差值一定在0~
     
      
       
        
         p
        
        
         −
        
        
         1
        
        
         之
        
        
         间
        
        
         。
        
       
       
        p-1之间。
       
      
     p−1之间。
 
     
      
       
        
         因
        
        
         为
        
        
         p
        
        
         的
        
        
         范
        
        
         围
        
        
         在
        
        
         l
        
        
         o
        
        
         n
        
        
         g
        
        
          
        
        
         l
        
        
         o
        
        
         n
        
        
         g
        
        
         以
        
        
         内
        
        
         ，
        
        
         所
        
        
         以
        
        
         只
        
        
         需
        
        
         要
        
        
         关
        
        
         心
        
        
         a
        
        
         ∗
        
        
         b
        
        
         和
        
        
         
          ⌊
         
         
          a
         
         
          ∗
         
         
          b
         
         
          /
         
         
          p
         
         
          ⌋
         
        
        
         ∗
        
        
         p
        
        
         在
        
        
         l
        
        
         o
        
        
         n
        
        
         g
        
        
          
        
        
         l
        
        
         o
        
        
         n
        
        
         g
        
        
         范
        
        
         围
        
        
         内
        
        
         的
        
        
         位
        
        
         ，
        
        
         更
        
        
         高
        
        
         的
        
        
         位
        
        
         一
        
        
         定
        
        
         是
        
        
         相
        
        
         同
        
        
         的
        
        
         。
        
       
       
        因为p的范围在long~long以内，所以只需要关心a*b 和left lfloor a*b/p right rfloor*p在long~long范围内的位，更高的位一定是相同的。
       
      
     因为p的范围在long long以内，所以只需要关心a∗b和⌊a∗b/p⌋∗p在long long范围内的位，更高的位一定是相同的。
 
 
时间复杂度分析 
 
 

     
      
       
        
         O
        
        
         (
        
        
         1
        
        
         )
        
       
       
        O(1)
       
      
     O(1)
 
 
代码实现 
#include

typedef long long ll;
typedef unsigned long long ull;

const int N = 1e5+10,M = N,INF = 0x3f3f3f3f,P = 998244353;


int main()
{
    std::ios::sync_with_stdio(false);
    ll a,b,p;
    std::cin>>a>>b>>p;
    a %= p,b %= p;
    ll c = (long double)a * b / p;
    ll res = a * b - c * p;
    if(res < 0)res += p;
    else if(res >= p)res -= p;
    std::cout< 
注意点 
为什么a和b要mod p？
 因为我们需要保证
     
      
       
        
         a
        
        
         ∗
        
        
         b
        
        
         /
        
        
         p
        
       
       
        a*b/p
       
      
     a∗b/p范围在long long内为什么用别的浮点数类型(double)会错？
 因为double的有效位数过小，在乘p以后导致错误
 例子：0.002 * 10000和0.0018 * 10000显然不同
 精度足够以后：
 0.0018 * 10000 和0.001811 * 10000不会影响为什么最后要有这一段代码？
 
if(res < 0)res += p;
else if(res >= p)res -= p;
 
因为在第一行对a和b mod p后，由模的性质可以知道最后答案可能会与原来的答案产生p的差值。
 
题目：
 64位整数乘法