[JSOI2009]瓶子和燃料【数论】

Pro

QwQ

Sol

手推几组数据就可以发现：答案即为k个数的gcd

所以爆搜出k个出，再暴力求gcd可以过部分数据……

正解好像和裴蜀定理有关：把n个数的因子都求出来，找出满足因子个数大于等于k的最大因子即为答案。

Code

爆搜代码

#include<iostream> #include<cstdio> using namespace std; int n , k , v[1005] , stack[1005] , top , ans; inline int mymax(int a , int b) { return a>b?a:b; } inline int gcd(int x , int y) { while(y) { int t = x%y; x = y; y = t; } return x; } int qgcd() { int res = gcd(stack[1] , stack[2]); for(int i=3; i<=top; i++) res = gcd(res , stack[i]); return res; } void dfs(int pre , int use , int aim) { if(use==aim) { ans = mymax(ans , qgcd()); return ; } for(int i=pre+1; i<=n; i++) { stack[++top] = v[i]; dfs(i , use+1 , aim); top--; } } int main() { scanf("%d%d",&n,&k); for(int i=1; i<=n; i++) scanf("%d",&v[i]); dfs(0 , 0 , k); printf("%d",ans); return 0; }

正解代码

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int n , k , num[1000005] , top , cnt = 1; void sol(int x) { for(int i=1; i<=sqrt(x); i++) { if(x%i==0) { num[++top] = i; if(i*i!=x) num[++top] = x/i; } } } int main() { scanf("%d%d",&n,&k); for(int i=1; i<=n; i++) { int x; scanf("%d",&x); sol(x); } sort(num+1 , num+top+1); for(int i=top-1; i; i--) { if(num[i]==num[i+1]) cnt++; else cnt = 1; if(cnt>=k) { printf("%d",num[i]); return 0; } } return 0; }