求为什么wa,谢谢大佬

P1618 三连击(升级版)

sqz11111 @ 2024-02-10 21:20:01

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

int a,b,c;
int num[9]={1,2,3,4,5,6,7,8,9},x,y,z;

int rnum(int x,int y,int z){
    return x*100+y*10+z;
}
int ist(int x,int y,int z){
    int stop=sqrt(max(max(x,y),max(y,z)));

    for(int i=1;i<=stop;i++){
        if(x%i==0)
            if(y%i==0)
                if(z%i==0)
                    x/=i,
                    y/=i,
                    z/=i;
    }

    if(x==a&&y==b&&z==c) return true;
    else return false;
}

int main(){
    cin>>a>>b>>c;

    while(next_permutation(num,num+9)){

        int one=rnum(num[0],num[1],num[2]);
        int two=rnum(num[3],num[4],num[5]);
        int three=rnum(num[6],num[7],num[8]);

        if(ist(one,two,three)){
            cout<<one<<' '<<two<<' '<<three<<endl;
        }
    }

    system("pause");
    return 0;
}

我的大概思路是使用next_permutation求所有组合,再用ist函数求是否符合 a:b:c 在样例里面只输出了 192 384 576

273 546 819


by 杜都督 @ 2024-02-10 22:05:02

  1. ist()里面的for,i<=z就好了,因为数据保证A<B<C

若无解,输出 No!!!

  1. next_permutation()会略过数组的原排列,所以你这样写无法处理输入数据为123:456:789的情况,可以考虑改用do-while或特判

by 杜都督 @ 2024-02-10 22:10:25

当然,对于这一题来说,你也可以选择删掉stop=后面的sqrt(),只选用最大值而不开根,最后效果也是一样的


by sqz11111 @ 2024-02-11 11:42:34

@杜都督 thanks


by sqz11111 @ 2024-02-11 12:05:47

@杜都督 ac了 蛤铪哈


by 杜都督 @ 2024-02-11 13:39:37

@sqz11111 不客气,开根一般是为了质数判断时减少循环次数服务的,但这题并不是质数判断,所以要老老实实除掉所有因数,如果开根的话就会有一半的因数没有被约分导致最终的比例不是最简的


by 杜都督 @ 2024-02-11 13:51:30

@sqz11111 当然,你的思路还可以再优化一点,简单一想就能想到,for的i<=a就够了,或者stop取三个数的 最小值 也可以


|