sgu 499 Greatest Greatest Common Divisor 约数“打表”

发布时间:2016-12-7 20:29:28 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"sgu 499 Greatest Greatest Common Divisor 约数“打表”",主要涉及到sgu 499 Greatest Greatest Common Divisor 约数“打表”方面的内容,对于sgu 499 Greatest Greatest Common Divisor 约数“打表”感兴趣的同学可以参考一下。

题目地址: http://acm.sgu.ru/problem.php?contest=0&problem=499 分析思路: 直接计算两两的最大公约数会超时的,我们换个角度看问题,我们找到输入进来的数的所有约数,如果某个数出现了两次或者以上,那么满足条件的最大的就是ggcd了 然后就是类似于筛法找约数,  这样可以找到 1~n中,每个数不超过自己平方根的所有约数。 然后比平方根大的那个可以用它除出来(完全平方数要特判了)。 然后不是暴力直接从最大的开始找出现过两次的,我们设置一个maxn来记录就好了,每次第二次出现的数和maxn比较一下就可以了。 先看代码: #include<iostream> #include<vector> #include<cmath> //#include<cstdio> using namespace std; #define N 1000005 vector<int> v[N+1]; //int cnt[N+1]={0}; bool b[N+1]={0}; void pre() { int len=sqrt(N); for(int i=1;i<=len;i++) for(int j=i*i;j<=N;j+=i) v[j].push_back(i); } int maxn=1; void check(int n) { if(b[n]) { maxn=n>maxn?n:maxn; } b[n]=1; } int main() { pre(); int size; cin>>size; for(int i=0;i<size;i++) { int n; cin>>n; if(n<=maxn) continue; for(int j=0;j<v[n].size();j++) { check(v[n][j]); if(v[n][j]*v[n][j]!=n) check(n/v[n][j]); } // int sqrtn=sqrt(n); // for(int j=1;j<=20&&j<=sqrtn;j++) // { // if(n%j==0) // { check(j); // // if(j*j!=n) check(n/j); // // } // } } // for(int i=1000000;i>0;i--) // if(cnt[i]>=2) // { // cout<<i<<endl; // break; // } cout<<maxn<<endl; } 这个是会超时的,因为每个数都有因子1,一般的数有因子2,我们在打表的时候选择不打前20个约数,然后针对输入进来的数(毕竟只有10w个少于数据范围100w),前20个检查一下就好了。  然后是,sqrt(n)不要出现在for(int i=0;i,<sqrt(n);i++) 这里, 先计算出来 ,不然每次判断都会去计算。  因为这个tle了几次。  在总是tle卡在test 20时 ,把所有cin cout 改成了scanf printf ,可以跑到test 38 还是改进皮毛呀   最后艰难ac了,代码: #include<iostream> #include<vector> #include<cmath> //#include<cstdio> using namespace std; #define N 1000005 vector<int> v[N+1]; //int cnt[N+1]={0}; bool b[N+1]={0}; void pre() { int len=sqrt(N); for(int i=21;i<=len;i++) for(int j=i*i;j<=N;j+=i) v[j].push_back(i); } int maxn=1; void check(int n) { if(b[n]) { maxn=n>maxn?n:maxn; } b[n]=1; } int main() { pre(); int size; cin>>size; // scanf("%d",&size); for(int i=0;i<size;i++) { int n; cin>>n; // scanf("%d",&n); if(n<=maxn) continue; for(int j=0;j<v[n].size();j++) { check(v[n][j]); if(v[n][j]*v[n][j]!=n) check(n/v[n][j]); } int sqrtn=sqrt(n); for(int j=1;j<=20&&j<=sqrtn;j++) { if(n%j==0) { check(j); if(j*j!=n) check(n/j); } } } // for(int i=1000000;i>0;i--) // if(cnt[i]>=2) // { // cout<<i<<endl; // break; // } cout<<maxn<<endl; // printf("%d\n",maxn); }

上一篇:ubuntu设置root密码
下一篇:HashMap的实现与优缺点

相关文章

相关评论