题解：P14992 取模

· · 题解

如果只用普通的加减乘除运算，似乎很难在不比较一个数和 M_2 大小关系的情况下，算出这个数模 M_2 的余数。所以自然要想办法比较 x_1 和 x_2 的大小，也就是如何表示 [x_1<x_2]。

有个公式是

[a<b]=\frac{(a-b)\bmod{2^{64}}-a+b}{2^{64}}

其中 0\le a,b<2^{64}。

我们在 \bmod M_1 意义下求出右式的值。

根据这个公式只需要算三项：(a-b)\bmod{2^{64}}，b-a，以及 \frac{1}{2^{64}} 在 \mod M_1 意义下的值。算第一项只需要利用一下自然溢出的特性。第二项可以直接算 kM_1+b-a，其中 kM_1\ge C。第三项因为 (M_1,2^{64})=(M_1,2)=1，所以 2^{64} 的逆元一定存在。因为 M_1\le 1.01\times 10^{9}，运算过程中不会爆 unsigned long long。

接下来考虑倍增，设 N=\left\lfloor\log_2\frac{C}{M_2}\right\rfloor，让 v_0 依次减去 M_2 2^N,M_2 2^{N-1},\ldots,M_2。每次减 M_22^i 只需要将 v_0 变为 v_0-[2^iM_2-1<v_0]2^iM_2。2^iM_2 是常数，不用单独用指令再去求。

语句条数约为 9\log_2{\frac{C}{M_2}}，内存甚至只用到了 2。

#include<bits/stdc++.h>
bool Mbg;
using namespace std;
#define int long long

void exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1;y=0;
        return;
    }
    exgcd(b,a%b,y,x);
    y-=a/b*x;
}
int n,M1,M2,C;
int iv;
void work(){
    cin>>n>>M1>>M2>>C;
    int a=((__int128)1<<64)%M1,x,y;
    exgcd(a,M1,x,y);
    iv=(x%M1+M1)%M1;

    if(C<M2){
        printf("v[0]=v[0]+0;\n");
        return;
    }
    int N=__lg(C/M2);
    for(int i=N;i>=0;i--){
        int B=M2<<i;
        printf("v[1]=%lld-v[0];\n",B-1); //a-b
        printf("v[1]=v[1]%%%d;\n",M1);
        printf("v[1]=v[1]+v[0];\n");
        printf("v[1]=v[1]+%d;\n",(-(B-1)%M1+M1)%M1);
        printf("v[1]=v[1]%%%d;\n",M1);
        printf("v[1]=v[1]*%d;\n",iv);
        printf("v[1]=v[1]%%%d;\n",M1);
        printf("v[1]=v[1]*%lld;\n",B);
        printf("v[0]=v[0]-v[1];\n");
    }
}
bool Med;
signed main(){
    int T=1;while(T--)work();
    // cerr<<"Time: "<<clock()<<" ms;\n";
    // cerr<<"Memory: "<<abs(&Med-&Mbg)/1024.0/1024.0<<" MiB.\n";
}