首页 > 代码库 > ACDream - k-GCD

ACDream - k-GCD

2024-07-13 23:13:21   218人阅读

先上题目：

B - k-GCD

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
SubmitStatus

Problem Description

   给出n个数a[1], a[2]...... a[n]和一个正整数k， 让你在这n个数中任取k个数并求它们的GCD， 问最大的GCD是多少。
   PS: k = 1时， GCD等于所选数本身。

Input

第一行一个整数T代表测试数据的组数。
每组测试数据有两行。
第一行有两个整数n, k；
第二行有n个整数a[1], a[2]...... a[n]:

1 <= T <= 100;
2 <= k <= n <= 10000;
1 <= a[i] <= 10000;

 

 

 

Output

每组数据输出一行，一个整数代表最大的GCD。

 

 

Sample Input

25 312 36 20 15 95 412 36 20 15 9

Sample Output

43

　　其实这一题原本不算难，但是为什么一开始会想不到？大概是脑子习惯地去想可能需要的时间复杂度要在O(n)~O(n^2)，然后就会很容易想到底是O(n)还是O(nlogn)还是O(n^2)，换而言之，我们很容易不去算时间复杂度而是下意识想题目的样子大概是什么时间复杂度，往往会忘了时间复杂度的提示就在题目里面，根本不用乱猜。
　　这一题的做法是把每一个数的每一个因子都求出来然后判断所有因子中，哪一种是大于等于k的，选最大的那个因子。时间复杂度只有O(n^(3/2))。

上代码：

 1 #include <cstdio> 2 #include <cstring> 3 #include <cmath> 4 #include <algorithm> 5 #define MAX 10002 6 using namespace std; 7   8 int a[MAX]; 9 int s[MAX];10 int maxn,mm,n,k;11  12 int main()13 {14     int t,sq,e;15     //freopen("data.txt","r",stdin);16     scanf("%d",&t);17     while(t--){18         memset(s,0,sizeof(s));19         scanf("%d %d",&n,&k);20         for(int i=0;i<n;i++) scanf("%d",&a[i]);21         mm=0;22         for(int i=0;i<n;i++){23             mm = max(a[i],mm);24             sq = (int)sqrt(a[i]*1.0);25             for(int j=1;j<=sq;j++){26                 if(a[i]%j==0){27                     s[j]++;28                     e = a[i]/j;29                     if(e != j)s[a[i]/j]++;30                 }31             }32         }33         maxn=0;34         for(int i=1;i<=mm;i++){35             if(s[i]>=k) maxn = i;36         }37         printf("%d\n",maxn);38     }39     return 0;40 }
k-GCD

 


联系
我们