A. Coprime Array

Coprime Array - 题目 - QOJ.ac

The 3rd Universal Cup. Stage 6: Osijek - A题

---

题型描述

分类讨论

题目描述

给定两个整数 $2<=s,x<=10^9$ 现在希望将 $s$ 分解为若干小于 $10^9$ 的整数之和，可以是负数，且这些整数与 $x$ 互质。

求至少要将 $s$ 分解成几个整数，并输出这些数。

题解

• $s$ 不能分解当且仅当 $gcd(x,s)=1$
• $s$ 分解成 $3$ 个数当且仅当 $s%2=1,x%2=0$
• 否则 $s$ 能分解成两个数

出于不知道什么原因，暴力搜索很快就能搜出来。

代码

#include <bits/stdc++.h>
using namespace std;
int s,x;
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
void solve(int s,int x)
{
	for(int i=0;;++i)
	{
		if(abs(gcd(i,x))==1&&abs(gcd(s-i,x))==1){
            printf("%d %d\n",i,s-i);
            return;
        }
	}
}
int main()
{
	scanf("%d%d",&s,&x);
	if(gcd(s,x)==1)printf("1\n%d\n",s);
	else if(s%2==1&&x%2==0)
	{
		printf("3\n1 ");
		solve(s-1,x);
	}
	else printf("2\n"),solve(s,x);
}