【gcd性质】EDU139 D. Lucky Chains

谁践踏了优雅 2024-03-22 13:12 36阅读 0赞

[Problem - 1766D - Codeforces][]

题意：

![d9cf04e3c1f347edb4f8d335d1e9c46f.png][]

思路：

感觉思路很好想，就是化简一下

![8999486cd94a4bdea5aafeff27ab2550.png][]

但是这里有个细节：这里直接分解质因数会T3

**当直接分解质因数T了的时候考虑先筛再分解 ，要仔细算算分解几个质因子**

Code：

#include <bits/stdc++.h>
    
    //#define int long long
    
    using namespace std;
    
    const int mxn=1e6+10;
    const int mod=998244353;
    
    int a,b,len=0;
    int prime[mxn],vis[mxn];
    
    void p_init(int n){
    	for(int i=2;i<=n;i++){
    		if(!vis[i]) prime[++len]=i;
    		for(int j=1;i<=n/prime[j];j++){
    			vis[i*prime[j]]=1;
    			if(i%prime[j]==0) break; 
    		}
    	}
    }
    void solve(){
    	cin>>a>>b;
    	if(__gcd(a,b)>1){
    		cout<<0<<'\n';
    		return; 
    	}
    	int ta=a;
    	if(a>b) swap(a,b);
    	int u=b-a;
    	int idx=1;
    	int ans=1e9;
    	while(prime[idx]<=sqrt(u)){
    		int p=prime[idx];
    		if(u%p!=0){
    			idx++;
    			continue;
    		}
    		while(u%p==0) u/=p;
    		ans=min(ans,p-a%p);
    		idx++;
    	}
    	if(u>1) ans=min(ans,u-a%u);
    	if(ans==1e9) cout<<-1<<'\n';
    	else cout<<ans<<'\n';
    }
    signed main(){
    	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    	int __=1;cin>>__;
    	p_init(1e6); 
    	while(__--)solve();return 0;
    }

[Problem - 1766D - Codeforces]: https://codeforces.com/problemset/problem/1766/D
[d9cf04e3c1f347edb4f8d335d1e9c46f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/69a25c27c98c45f09fa4747df2015615.png
[8999486cd94a4bdea5aafeff27ab2550.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/27d2d9e7291d4336bb6381b09767af22.png

发表评论取消回复

表情：

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

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

相关阅读

相关 Atcoder ABC 139D

Atcoder ABC 139D 解法： > 等差数列求和公式，记得开 $ long long $ CODE: include<iostre...

末蓝、/ 2024年04月20日 10:31/ 0 赞/ 96 阅读

相关【gcd性质】EDU139 D. Lucky Chains

[Problem - 1766D - Codeforces][] 题意： ![d9cf04e3c1f347edb4f8d335d1e9c46f.png][] 思路：感

谁践踏了优雅/ 2024年03月22日 13:12/ 0 赞/ 37 阅读

相关【组合数学】EDU143 D. Triangle Coloring

独立思考的时候想的思路和正解差不多！只不过缺点细节感觉得多写写1600+的题，这样才能进步！ [Problem - D - Codeforces][] 题意： ![

╰半夏微凉°/ 2024年03月22日 12:34/ 0 赞/ 57 阅读

相关【gcd性质】最小公倍数挑战

[题目-最小公倍数挑战 (51nod.com)][-_ _51nod.com] 题意： ![6a3b4ea39a0d451480358cb55741a9e0.png][]

绝地灬酷狼/ 2024年03月22日 09:30/ 0 赞/ 31 阅读

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

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

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

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

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

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

相关【倒着考虑】CF Edu 21 D

[Problem - D - Codeforces][] 题意： ![c2e913d33a044e77bf92a4cd9a8c19f3.png][] 思路：这道题需要

约定不等于承诺〃/ 2024年03月09日 00:44/ 0 赞/ 98 阅读

相关【简单几何】CF Edu11 D

[Problem - D - Codeforces][] 题意： ![dc204ef2a0e44465bfc3ca02f80670ee.png][] 思路：和蓝桥杯国

拼搏现实的明天。/ 2024年03月08日 08:21/ 0 赞/ 99 阅读

相关【构造】CF Edu 12 D

[Problem - D - Codeforces][] 题意： ![c938d4045d17475f9e3ed23edf020b4f.png][] 思路：这种题一定

谁践踏了优雅/ 2024年03月08日 08:06/ 0 赞/ 112 阅读

相关 codeforces 146D Lucky Number 2 (找规律)

Petya loves lucky numbers very much. Everybody knows that lucky numbers are positive int

￡神魔★判官ぃ/ 2022年06月04日 06:45/ 0 赞/ 225 阅读