【gcd性质】猫猫与数学

叁歲伎倆 2024-03-22 09:05 94阅读 0赞

[E-猫猫与数学\_牛客小白月赛71(重现赛) (nowcoder.com)][E-_71_ _nowcoder.com]

题意：

![16f764afa4244227af627671df142e8d.png][]

思路：

首先考虑题目给出的条件里可以操作的地方（特殊性质）

gcd

1e14

对于gcd，既然它不为1，那么我们就可以设它为p

然后gcd(a+c,b+c)，很容易想到更相减损法来处理

对于1e14这个特殊范围，一般都是去枚举因子

具体做法如下：

![d88248f8879a4f0ebb8fedeb74818456.jpeg][]

Code：

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll a,b;
    int main(){
        cin>>a>>b;
        if(a==b){
            if(a==1){
                cout<<"1";
            }
            else{
                cout<<"0";
            }
            return 0;
        }
        if(a>b)swap(a,b);
        if(b-a==1)cout<<"-1";
        else{
            if(__gcd(a,b)>=2){
                cout<<"0";
            }
            else{
                ll x=b-a;
                ll res=1e18;
                
                map<ll,ll>mp;
                for(ll i=1;i*i<=x;i++){
                    if(x%i==0){
                        mp[i]++;
                        if(x/i!=i)mp[x/i]++;
                    }
                }
                for(auto &c:mp){
                    
                    ll x=c.first;
                    if(x==1)continue;
                    res=min(res,(x-a%x)%x);
                }
                cout<<res;
            }
        }
        return 0;
    }

[E-_71_ _nowcoder.com]: https://ac.nowcoder.com/acm/contest/56661/E
[16f764afa4244227af627671df142e8d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/9a35200d6cb24efcb6be9027b9d4a2f0.png
[d88248f8879a4f0ebb8fedeb74818456.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/f4f3bf5a2eed462ba2cbc3bcc92f9e99.png

发表评论取消回复

表情：

评论列表（有 0 条评论，94人围观）

还没有评论，来说两句吧...

相关阅读

相关【gcd性质】Lcm和Gcd的构造

[题目-Lcm与Gcd构造 (51nod.com)][-Lcm_Gcd_ _51nod.com] 题意： ![8bd68069802b42819bbd3ddf6b152d6

雨点打透心脏的1/2处/ 2024年03月22日 09:23/ 0 赞/ 72 阅读

相关【gcd性质】猫猫与数学

[E-猫猫与数学\_牛客小白月赛71(重现赛) (nowcoder.com)][E-_71_ _nowcoder.com] 题意： ![16f764afa4244227af

叁歲伎倆/ 2024年03月22日 09:05/ 0 赞/ 95 阅读

相关【离线】牛客小白月赛71 D-猫猫与主人

还是不懂离线算法，感觉不是很会啊 [D-猫猫与主人\_牛客小白月赛71(重现赛) (nowcoder.com)][D-_71_ _nowcoder.com] 题意： ![

蔚落/ 2024年03月22日 09:04/ 0 赞/ 84 阅读

相关 20190612 叠猫猫赚金币最新脚本

1、使用chrome浏览器、或者360极速浏览器，360极速模式等； 2、打开 [https://login.m.taobao.com/login.htm][https_lo

雨点打透心脏的1/2处/ 2024年01月20日 08:12/ 0 赞/ 43 阅读

相关猫脸变换

Arnold这个名字由来是一个叫做Arnold的前辈提出的一种变换，最初是用一只猫图片进行了该变换，所以也叫猫脸变换，这种映射可以把图像的各像素点位置进行置换，也就是说通过

骑猪看日落/ 2023年06月04日 06:52/ 0 赞/ 36 阅读

相关章鱼猫（Octocat）

为什么Github的Logo是一只章鱼猫呢？ ![1395907-20190821225634319-785516448.png][] Reference： [章鱼

短命女/ 2023年06月01日 06:18/ 0 赞/ 24 阅读

相关为网站页面添加live2D小猫猫

live2D是一种应用于电子游戏的绘图渲染技术，技术由日本Cybernoids公司开发，通过一系列的连续图像和人物建模来生成一种类似三维模型的二维图像。 live2d官方提供

Bertha 。/ 2023年02月12日 05:49/ 0 赞/ 31 阅读

相关猫公子xiu

姓名：休休，年龄一岁半（2019-02-28出生），美短虎斑猫，性格温和、乖巧，玩的时候也很调皮，不怕生，吃得多（好吃鬼、母老虎），以下是我精美的照片，喜欢的记得点赞哦。

柔光的暖阳◎/ 2022年11月26日 07:59/ 0 赞/ 185 阅读

相关短信猫 Java

短信发送  <bean id="SMSServiceTask" class="com.comname.smp.co

落日映苍穹つ/ 2022年08月04日 13:50/ 0 赞/ 290 阅读

相关 ERC721标准与加密猫

2017 年 11 月 28 日，“加密猫”游戏出现在互联网上。这是基于以太坊的 ERC721 标准（不可互换通证）发行的加密数字宠物，每一只猫咪各不相同。加密猫的正式...

朱雀/ 2020年10月07日 08:28/ 0 赞/ 2123 阅读