https://www.zhihu.com/question/56657137/answer/149930298
https://scut.online/problem.php?id=74
求逆元运算

题目描述
METO 喜欢正方形，于是他希望在格点纸上画出尽可能多的正方形。

已知 METO 有一张 n*m,(1 \le n,m \le 10^9)

n∗m(1≤n,m≤10​9​​) 的格点纸，正方形的定义是四条边相等，且内角均为 90 度，请你帮他计算能画出多少个正方形。

输入格式
第一行为数据组数 T,(1 \le T \le 100)

T(1≤T≤100)接下去 T

T 行，每行两个正整数 n,m,(1 \le n,m \le 10^{9})

n,m(1≤n,m≤10​9​​)

输出格式
对每组数据输出一行 ans

ans，表示最多能画出正慌形的个数，答案对 10^9+7

10​9​​+7 取模

样例数据
输入
32 43 44 4
输出
31020

#include<stdio.h>
#include<algorithm>
#include <string.h>
using namespace std;
const long long mod=1000000007;
typedef long long LL;
LL rever[10];
LL fast_multi(LL a,LL b,LL mod)
{
    LL res=0,base=a;
    while(b)
    {
        if(b&1) res=(res+base)%mod;
        b>>=1;
        base=(base+base)%mod;
    }
    return res;
}
LL pow_mod(LL a,LL b,LL mod)
{
    LL res=1,base=a;
    while(b)
    {
        if(b&1) res=fast_multi(res,base,mod);
        base=fast_multi(base,base,mod);
        b>>=1;
    }
    return res;
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(b==0)
    {
        x=1;
        y=0;
        return a;
    }
    LL gcd=exgcd(b,a%b,x,y);
    LL temp=x;
    x=y;
    y=temp-a/b*y;
    return gcd;
}
LL reverseMod(LL a,LL mod)
{
    LL x,y;
    LL d=exgcd(a,mod,x,y);
    while(x<0) x+=mod;
    return x;

}
int main()
{
    for(LL i=2;i<=8;i++)
    {
        rever[i]=reverseMod(i,mod);
    }
   int t;
   scanf("%d",&t);
   LL n,m,r,ans;
   while(t--)
   {
       scanf("%lld%lld",&n,&m);
       r=min(n,m);
       ans=(rever[4]*pow_mod(r,4,mod)+rever[2]*pow_mod(r,3,mod)+rever[4]*fast_multi(r,r,mod)
            -fast_multi(n+m,(rever[3]*pow_mod(r,3,mod)+rever[2]*fast_multi(r,r,mod)+rever[6]*r),mod)
            +fast_multi(n*m,rever[2]*fast_multi(r,r,mod)+rever[2]*r,mod))%mod;
            printf("%lld\n",ans);
   }
}