欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

[扩展欧拉函数] 牛客2020多校第三场 F.Fraction Construction Problem

程序员文章站 2022-03-11 15:03:32
题目已知ab 求出符合条件的cdef思路先想想a/b是不是最简形式如果gcd(a,b)!= 1则可令c/d=a2/b2+1 e/f=1即 c=(a+b)/gcd(a,b) d=b/gcd(a,b) e=1,f=1如果gcd(a,b)==1则(cf-ed)/df=a/b令df=b cf-ed=a如果知道df 则ce可根据扩展欧几里得求出那么df最好是互质的先令d为b的一个质因子 然后求出f (详见代码)最后根据exgcd计算出ce代码#include

题目

[扩展欧拉函数] 牛客2020多校第三场  F.Fraction Construction Problem

已知ab 求出符合条件的cdef

思路

先想想a/b是不是最简形式

  • 如果gcd(a,b)!= 1
    则可令c/d=a2/b2+1 e/f=1
    即 c=(a+b)/gcd(a,b) d=b/gcd(a,b) e=1,f=1
  • 如果gcd(a,b)==1
    则(cf-ed)/df=a/b
    令df=b cf-ed=a
    如果知道df 则ce可根据扩展欧几里得求出
    那么df最好是互质的
    先令d为b的一个质因子 然后求出f (详见代码)
    最后根据exgcd计算出ce

代码

#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