当前位置: 代码迷 >> 综合 >> F. Fractions(exgcd)
  详细解决方案

F. Fractions(exgcd)

热度:13   发布时间:2024-02-11 22:50:28.0

在这里插入图片描述
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;
}
  相关解决方案