已知ab 求出符合条件的cdef
先想想a/b是不是最简形式
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<cctype>
#include<ctime>
#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<iomanip>
#include<list>
#include<bitset>
#include<sstream>
#include<fstream>
#include<complex>
#include<algorithm>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ll long long
using namespace std;
const int INF = 0x3f3f3f3f;
vector<int> v;
bool vis[2000010];
int vis1[2000010];
ll exgcd(ll a,ll b,ll &x1,ll &y1){
if(b==0){
x1=1;
y1=0;
return a;
}
int g=exgcd(b,a%b,x1,y1);
int temp=x1;
x1=y1;
y1=temp-(a/b)*y1;
return g;
}
void p(int n){
memset(vis,0,sizeof vis);
for(int i=2;i<n;i++){
if(!vis[i]){
v.push_back(i);
vis1[i]=i;
}
for(int j=0;j<v.size()&&i*v[j]<n;j++){
vis[i*v[j]]=1;
vis1[i*v[j]]=v[j];
if(i%v[j]==0) break;
}
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t;
cin>>t;
p(2000010);
vis1[1]=1;
// for(int i=1;i<=100;i++) cout<<i<<" "<<vis1[i]<<endl;
while(t--){
ll a,b;
cin>>a>>b;
if(b==1) cout<<"-1 -1 -1 -1"<<endl;
else{
ll gcd=__gcd(a,b);
if(gcd>1){
cout<<(a+b)/gcd<<" "<<b/gcd<<" "<<1<<" "<<1<<endl;
}
else{
//cout<<2<<endl;
ll d1=vis1[b];
ll d=1,f=b;
while(f%d1==0){
d*=d1,f/=d1;
}
//cout<<d<<" "<<f<<endl;
if(f==1){
cout<<"-1 -1 -1 -1"<<endl;
continue;
}
ll c,e;
exgcd(d,f,c,e);
c=-c;
//cout<<c<<" "<<e<<endl;
while(c<=0||e<=0){
c+=f,e+=d;
}
c*=a,e*=a;
cout<<e<<" "<<d<<" "<<c<<" "<<f<<endl;
}
}
}
return 0;
}
本文地址:https://blog.csdn.net/kosf_/article/details/107521415
如对本文有疑问, 点击进行留言回复!!
android RecyclerView checkbox复用解决
Android Q Input (1) -- InputManagerService启动
android -- ndk (stack corruption detected)
Android Span富文本图文混排 - ImageSpan(图文垂直居中)
网友评论