Fractions 猜公式+扩展gcd

程序员文章站 2022-06-08 12:28:41

...

Fractions

题意：

给一个n，构建一个序列，使得满足这3个条件
$\begin{cases} \sum_{i=1}^k \frac{a_i}{b_i}=1-\frac{1}{n}\\ 1\leqslant a_i<b_i\\ b_i 是n的因子，且1<b_i<n \end{cases}$

原题：

题目来源 ICPC Northeastern European Regional Contest 2018

（链接不好找，计蒜客里复现赛里的）

Fractions 猜公式+扩展gcd

解题分析：

猜公式：经过实验观察，对于任意m，只要m不是质数，b= $\frac{m}{a}$ , 那么 ax+by=n-1 就能成立。
证明公式，

假设
$\frac{x·a}{n}+\frac{y·\frac{n}{a}}{n}=\frac{n-1}{n} 成立$
那么也就是
$x·a+y·\frac{n}{a}=n-1$
若gcd(a, $\frac{n}{a}$ )=1,则必定存在 $x_1·a+y_1·\frac{n}{a}=1$ ， n-1是1的倍数，则 $x_2·a+y_2·\frac{n}{a}=n-1$

若gcd(a, $\frac{n}{a}$ )$\neq$1,

假设 $x_2·a+y_2·\frac{n}{a}=n-1$ 成立

那么 $x_2·a^2+y_2·n=(n-1)a$

$又\because gcd(a^2,n)=a*f, f是n的因数，且f\neq 1$

$\therefore (n-1)·a %gcd(a^2,n) = (n-1)%f \neq 0 $

$\therefore 当gcd(a,\frac{n}{a} )\neq1$

$比如gcd（2^2，20)=4$

综上所述，可以证得只有当 gcd(a, $\frac{n}{a}$ )=1时，必然能使得 $x·a+y·\frac{n}{a}=n-1$ 有整数解。
证明有必定存在x和y都是正数使得 $x·a+y·\frac{n}{a}=n-1$ 成立，记 b= $\frac{n}{a}$ ， $x_0$ 是（2）下的x的最小正整数解
$b·a+0·b=n \quad(1)\\ x_0·a+y_0·b=1 \quad(2)\\$
$\because (2)中x_0>0.且a>1,b>1,易知y_0<0$

$又\because x=x_0+\frac{b}{gcd(a,b)}*k, x_0=x\%b,故而x_0<b$

$\therefore (1)-(2)得 (b-x_0)·a-y_0·b=n-1,则此时 (b-x_0)>0,\quad -y_0>0,证毕！$

而既然必定存在，那么只要找到 $x·a+y·\frac{n}{a}=n-1$ 的最小正整数解就可以，因为在相加情况下存在，一个小了，另一个不是更有可能是正数么。

求 $x·a+y·\frac{n}{a}=n-1$ 的最小正整数解，其中 a>=0, $\frac{n}{a}>=0$ ，符合扩展欧几里德的使用条件。

代码

算法步骤

对n分解，分解成 $n=p_1^{m_1}p_2^{m_2}...$ 的形式(p是素数)，取a= $p_1^{m_1}$
令 $b=\frac{n}{a},c=n-1$ 带入exgcd求解，得到x和y之后，做最小正整数处理

#include "bits/stdc++.h"
using namespace  std;
#define ll long long
int exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){x=1;y=0;return  a;}
    int r=exgcd(b,a%b,x,y);
    int tem=x;
    x=y;
    y=tem-a/b*y;
    return r;
}

int  main()
{
    int n;
    scanf("%d",&n);
    int fac=0,nn=n,size=0;
    for(int i=2;i*i<=nn;++i)
    {
        if(nn%i==0) {
            int tem = 1;
            while (nn % i == 0) {
                nn /= i;
                tem *= i;
            }
            if (!fac)fac = tem;   //只要找到一个就行
            size++;
        }
    }
    if(nn>1)size++;

    if(size<=1)puts("NO");
    else {
        puts("YES");
        puts("2");

        int a=fac,b=n/fac,c=n-1;       //此处开始套公式，ax+by=c  ，最小正整数解x=x*c%( b/gcd(a,b))
        ll x,y;                     // 一定要用long long，不然在使用exgcd的时候会wa
        int gcd=exgcd(a,b,x,y);
        int mod=b/gcd;
        x=(x*c/gcd %mod+mod)%mod;    //防止负数
        y=(c-a*x)/b;
        printf("%d %d\n%d %d\n",x,n/a,y,n/b);
    }
return 0;
}