友好地数数字数字友好数字

Question

这个的时间限制非常严格，我的代码有50%的例子过不去不知道思路有什么问题

Answer 1

你试试下面的代码吧：

#include <stdio.h>
#include <math.h>
int gcd(long long a,long long b){ //求a和b的最大公约数
    if(b ==0)return a;
    return gcd(b,a%b);
}
int isprime(int n){ //判断n是否是质数
    for(int i=2;i<=sqrt((double)n);i++){
        if(n%i==0)
            return 0;
    }
    return 1;
}
int main() {
    int n, i, j, found = 0;
    int s[100];
    long long k = 1;
    int m = 0;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &j);
        if(isprime(j)) //如果是质数，k直接相乘
            k*=j;
        else{
            if(j%2==0){ //如果j是偶数
                if(k%2!=0) //k不包含因子2
                    k*=2;
            }else
                s[m++] = j;
        }
    }
    if(n==1)
    {
        printf("%d",s[0]);
        return 0;
    }

    //如果k=1，说明全是S中全是奇数，且没有质数，所以从3开始遍历
    if(k==1){
        k = 3; //从3开始遍历所有奇数
        for(;!found;k+=2){
            int isfriend = 1;
            for(i=0;i<m;i++){
                if(gcd(k,s[i]) == 1){ //公约数只有1
                    isfriend = 0; //不是友好数，跳过，继续下一循环
                    break;
                }
            }
            //如果没有偶数，那么js=n，上面的for循环可以遍历所有的s元素
            //如果有偶数，因为所有偶数的公因子都是2，所以，只需要找到一个
            //能与所有奇数有公因子，且是2的倍数的数即可
            if(isfriend){
                printf("%lld",k);
                found = 1;
            }
        }
    }else{
        //k!=1,说明当前k是s中所有质数的乘积，要求的最小友好数一定是当前k的倍数，
        long long minK = 0; //要求的最小友好数
        for(;!found;){
            minK += k;
            int isfriend = 1;
            for(i=0;i<m;i++){
                if(gcd(minK,s[i]) == 1){ //公约数只有1
                    isfriend = 0; //不是友好数，跳过，继续下一循环
                    break;
                }
            }
            //如果没有偶数，那么js=n，上面的for循环可以遍历所有的s元素
            //如果有偶数，因为所有偶数的公因子都是2，所以，只需要找到一个
            //能与所有奇数有公因子，且是2的倍数的数即可
            if(isfriend){
                printf("%lld",minK);
                found = 1;
            }
        }
    }
    return 0;
}