Fractions

In the first line print “YES” if there exists such a sequence of fractions or “NO” otherwise.
If there exists such a sequence, next lines should contain a description of the sequence in the following format.
The second line should contain integer k (1 ≤ k ≤ 100 000) — the number of elements in the sequence. It is guaranteed that if such a sequence exists, then there exists a sequence of length at most 100 000.
Next k lines should contain fractions of the sequence with two integers a_i and b_i on each line.

C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 500K, 提交时间: 2020-10-06 13:35:03

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int p = 1e9 + 7;

int main()
{
    ll n;
    scanf("%lld",&n);
    ll m=n-1;

    ll x=1;
    for(ll i=2;i*i<=n;i++){
        if(n%i) continue;
        while(n%i==0) x*=i,n/=i;
        break;
    }

    if(n==1||x==1){
        cout<<"NO"<<endl;
        return 0;
    }
    for(int i=1;i<x;i++){
        if((m-n*i)%x==0){

            printf("YES\n2\n");
        cout<<i<<" "<<x<<endl;
        cout<<(m-n*i)/x<<" "<<n<<endl;
        }
    }

}

C++(clang++11) 解法, 执行用时: 10ms, 内存消耗: 504K, 提交时间: 2020-10-26 22:05:29

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll n;

int main()
{
	scanf("%lld",&n);
	for (ll i=2;i<=sqrt(n);i++)
		if(n%i==0)
			for (ll j=1;j<i;j++)
				if((n-1-j*n/i)%i==0)
				{
					printf("YES\n2\n%lld %lld\n%lld %lld\n",j,i,(n-1-j*n/i)/i,n/i);
					return 0;
				}

	puts("NO");

	return 0;
}

详情