D. Three Integers

题目

给你三个数a，b，c，可以把a，b，c，进行+1.或者-1操作，最多减到1，问最少多少次操作能让a能整除b，b能整除c，并输出任意一组满足要求的a,b,c.

分析

这题我从一开始就想到枚举b，因为好多三个数的题，中间的数因为是和前后关联着，所以枚举他比较好。我的大致思路是，枚举从1到20000枚举b，a必定是b的一个因子，所以我们枚举因子,至于c，要能整除，c必定要变成(c/b)*b或者(c/b+1)*b，所以就这样枚举就可以了。复杂度,650ms过的，1e8的复杂度2s也是能过的。
因为最极端的情况下，整除关系也不会超过这样10000 20000 40000，所以遍历到20000保险一些

AC代码

#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 1e9;
int T,a,b,c;

void solve(){
    int cnt = inf;
    int aa = -1,bb = -1,cc = -1;
    for(int i = 1;i<=20000;i++){
        int dis,disa = inf,disb = abs(b-i),disc = inf;
        int cura = a,curb = i,curc = b;
        for(int j = 1;j*j<=i;j++){ //枚举因子
            if(i%j == 0){
                if(abs(a-j)<disa){
                    cura = j;
                    disa = abs(a-j);
                }
                int j2 = i/j;
                if(abs(a-j2)<disa){
                    cura = j2;
                    disa = abs(a-j2);
                }
            }
        }
        int t1 = c/i*i,t2 = c/i*i+i; //c的两种情况
        if(abs(t1-c) < disc){
            disc = abs(t1-c);
            curc = t1;
        }
        if(abs(t2-c) < disc){
            disc = abs(t2-c);
            curc = t2;
        }
        dis = disa+disb+disc;
        if(dis < cnt){
            cnt = dis;
            aa = cura,bb = curb,cc = curc;
        }
    }
    printf("%d\n",cnt);
    printf("%d %d %d\n",aa,bb,cc);
}
int main(){
    cin>>T;
    while(T--){
        scanf("%d%d%d",&a,&b,&c);
        solve();
    }
    return 0;
}