美文网首页
METO与他的正方形

METO与他的正方形

作者: Gitfan | 来源:发表于2017-03-28 11:15 被阅读0次

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);
   }
}

相关文章

  • METO与他的正方形

    https://www.zhihu.com/question/56657137/answer/149930298h...

  • 披萨分割

    题目描述METO 喜欢吃披萨,同时他又是一个对几何美学颇有研究的人。 对于一个披萨,METO 首先会在边缘随机取 ...

  • 飘飘的ScalersTalk第五轮新概念朗读持续力训练Day 4

    练习材料: Last week at a dinner-party, the hostess asked meto...

  • Mr. C-19

    Tonight you belong to meto me onlywhen I declare this I w...

  • 千变万化的div

    平平无奇的正方形与长方形 正方形与长方形没什么好介绍的,因为这个是本色演出。1. 正方形 长方形 各种圆 包括正圆...

  • 圆形与正方面积比值相关比值相关规律

    1、在正方形内画最大圆,正方形的面积与圆的面积比值是1:0.785。 因为正方形面积=边长X边长,,圆面积=πr²...

  • OpenGL 正方形渲染与移动

    三角形渲染 OpenGL正方形渲染与移动 渲染 将正方形顶点存储在全局数组GLfloat vVerts[] = {...

  • 鱼与正方形

    池塘里有一条离群索居的哲学家鱼。这天他突然说:“愚蠢的鱼啊,你们整天成群结队、游来游去,却不知道,你们不过是生活在...

  • 面试题 16.13. 平分正方形

    题目描述 给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。假设正方形顶边和底边与 x 轴平...

  • 长方形与正方形

    长方形与正方形 教学目标: 1、 结合观察、操作活动,能够用自然的语言描述长方形和正方形的特征。 2、 了解折、画...

网友评论

      本文标题:METO与他的正方形

      本文链接:https://www.haomeiwen.com/subject/uwcjottx.html