【gcd性质】猫猫与数学

叁歲伎倆 2024-03-22 09:05 61阅读 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 条评论，61人围观）

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

相关阅读

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

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

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

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

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

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

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

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

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

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

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

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

相关猫公子xiu

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

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

相关短信猫 Java

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

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

相关猫狗队列题目

源码下载链接:[https://github.com/huijuanl/AlgorithmLearning.git][https_github.com_huijuanl_Alg

桃扇骨/ 2022年05月22日 11:45/ 0 赞/ 262 阅读

相关作文以别猫

猫祭吾家曾有小猫咪，身着黑白显虎威，怎奈娇弱小身躯，常在人前妙哀呼。想是灵物落人间，柔声律足善歌舞。不求扑鼠尺寸功，唯爱弄花与戏蝶。

爱被打了一巴掌/ 2022年05月20日 02:11/ 0 赞/ 153 阅读

相关猫狗数据集

import numpy as np import pickle import cv2 import pandas as pd import tensorflow as

怼烎@/ 2021年11月24日 02:10/ 0 赞/ 501 阅读

相关 ERC721标准与加密猫

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

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