51nod-1179 最大的最大公约数

    xiaoxiao2025-01-31  11

    原题链接

    1179 最大的最大公约数 题目来源:  SGU 基准时间限制:1 秒 空间限制:131072 KB 分值: 40  难度:4级算法题  收藏  关注 给出N个正整数,找出N个数两两之间最大公约数的最大值。例如:N = 4,4个数为:9 15 25 16,两两之间最大公约数的最大值是15同25的最大公约数5。 Input 第1行:一个数N,表示输入正整数的数量。(2 <= N <= 50000) 第2 - N + 1行:每行1个数,对应输入的正整数.(1 <= S[i] <= 1000000) Output 输出两两之间最大公约数的最大值。 Input示例 4 9 15 25 16 Output示例 5

    #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <vector> #include <map> #include <cmath> #include <queue> #define MOD 998244353 #define maxn 50005 #define INF 1e18 using namespace std; typedef long long ll; int vis[1000005]; int main(){ // freopen("in.txt", "r", stdin); int n; while(scanf("%d", &n) == 1){ int a; memset(vis, 0, sizeof(vis)); for(int i = 0; i < n; i++){ scanf("%d", &a); vis[a] = 1; } int maxs = 1; for(int i = 2; i <= 1000000; i++){ int cnt = 0; for(int j = i; j <= 1000000; j += i){ if(vis[j]) cnt++; if(cnt == 2) break; } if(cnt == 2) maxs = i; } printf("%d\n", maxs); } return 0; }

    转载请注明原文地址: https://ju.6miu.com/read-1295964.html
    最新回复(0)