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

F. Fractions(exgcd)

程序员文章站 2022-06-08 12:23:26
...

F. Fractions(exgcd)
bi 是n的因数,且ai<bi;
ai/bi+…+=n-1/n;
首先我们先变形一下
a1/b1+a2/b2+…+ai/bi=(n-1)/n
同乘n,(bi是n的因数,n/bi为整数)令ci=n/bi;
变为: a1c1+a2c2+…+aici=n-1;
因为ci也是n的因子,这里用到一个定理: ci 是n 的因子,则ci一定能用一个n的质因子的倍数表示出来。 因为任意一个数都能用多个质数相乘表示(除了1以外)。假设di 是n的质因子,且能表示出ci=ei
di。
变为a1*(d1e1)+a2(d2e2)+…+ai(diei)=n-1;
此时上式中的每一项都是n的质因子的倍数,一个质数可以由两个小的质数倍数相加表示出来。取两个n的质因子a,b。且a
b=n;
最后可以表示成ax+by=n-1
由exgcd 得知,ax+by=n-1有解的话必须是g=gcd(a,b)整倍数;
用exgcd 求出x,y ,此时求出的解是ax+by=g;的
变型:ax*(n-1)/g+by*(n-1)/g=n-1;
两边再除以n,得出
(a/n)*(n-1)x/g+(b/n)(n-1)*y/g=n-1/n
a/n=1/b; b/n=1/a;
xx=(n-1)*x/g,yy=(n-1)*y/g;
所以最后结果!!!!

xx/b+yy/a=n-1/n;

#include<queue>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<math.h>
#include<stdlib.h>
#include<stack>
#include<stdio.h>
#include<vector>
#include<map>
#include<string.h>
#define ll long long
#define db double
#define F(n) for(int i=1;i<=n;i++)
using namespace std; 
const int mx=1e5+10, mod = 998244353;
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;	
} 
ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		x=1,y=0;
		return a;
	}
	ll g=exgcd(b,a%b,x,y);
	ll tp=x;
	x=y;
	y=tp-a/b*y;
	return g;
}
int main()
{
	ll n,flag=0;
	scanf("%lld",&n);
	ll nn=sqrt(n);
	for(int i=2;i*i<=n;i++){
		if(n%i==0){
			ll a=i,b=n/i;
			ll g=gcd(a,b);
			if((n-1)%g==0&&a!=b){
				ll tx,ty;
				exgcd(a,b,tx,ty);
				tx=tx*(n-1)/g;
				ty=ty*(n-1)/g;
				while(tx<0){
					tx+=b;
					ty-=a;
				} 
				while(ty<0){
					tx-=b;
					ty+=a;
				}
				flag=1;
				printf("YES\n2\n%lld %lld\n%lld %lld\n",ty,a,tx,b);
				break;
			}
		}
	}
	if(flag==0) printf("NO\n");
	return 0;
}