題意：給你一個數字x，把x至少拆分為兩個數的和，并且這些數字互質，問所有拆分方案中，在每個方案中最大值減去最小值的最小值是多少
思路：
算是一個構造題吧，
①如果x是奇數，那么拆分為x/2和x-x/2，答案是1
②如果x是偶數并且x/2是偶數，，那么可以分成x/2+1，x/2-1這是分成了兩個奇數，一定互質，答案是2
③如果x是偶數并且x/2是奇數，那么我們對x取余3進行判斷，
如果是3的倍數，比如42，可以拆成13 14 15.那么答案是2
如果取模3后余1，比如70 可以分成22 23 25 答案是3
取模3余2，比如62 可以分成19 21 22 答案是3
按照上面構造方式 判斷一下是不是兩兩互質即可
容易發現答案最多為4，因為如果x是偶數，x/2是奇數，那么只需要拆分為x/2-2、x/2+2即可
④注意特判x=6時候無解
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
signed main(){
int T;scanf("%d",&T);int ca=0;
while(T--){
int ans=4;
int x;cin>>x;
if(x==6) ans=-1;
else if(x&1) ans=1;
else{
int k=x/2;
if(k%2==0) ans=2;
else{
ans=min(ans,x-k);
if(x%3==0) ans=min(ans,2);
else if(x%3==1){//70 22 23 25
int q=x/3,w=q+2,e=q-1;
if(__gcd(q,w)==1 && __gcd(q,e)==1 && __gcd(w,e)==1) ans=min(ans,3);
}
else {//62 19 21 22
int q=x/3-1,w=q+2,e=q+3;
if(__gcd(q,w)==1 && __gcd(q,e)==1 && __gcd(w,e)==1) ans=min(ans,3);
}
}
}
printf("Case #%d: %d\n",++ca,ans);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/202840.html
標籤：其他