的循环节长度原来有陷阱,题目并没有规定 i必须小于 j,对于 i>j 的情形需要交换 i和j的顺序再进行寻找。现在就可以 AC 了! 2017-3-10 7更多的问题: 更改后的代码怎么写? 输入数据中的 i和j的要求改为 0<i,j<1 000 000 怎么办? 还能那样求吗?小心 TLE! 详情见 Uva 的100 题: http://uva./index.php?_onlinejudge&Itemid=8&c ategory=3&page=show_problem&problem=36 2017-3-10 8 poj2773 Happy 2006 题目大意就是给出 n和k求出第 k个与 n互素的数(1 <= n <= 1000000), k (1 <= k <= 100000000). Input : n ,k Output : 第k个与 n互素的数 Sample Input 2006 1 2006 2 2006 3 Sample Output 135 2017-3-10 9 分析题目难点 1:题目特点 2:如何判读两个数互素 3:如何快速求两个数的最大公约数数据大,传统的循环到第 k个数一定会超时互素说明两个数的最大公约数为 1 以前的从 2循环到 sqrt(n) 肯定不行,会超时这里要用到欧几里德算法: gcd(a,b)=gcd(b,a%b) int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }见《算法入门竞赛经典》第 177 页 int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }见《算法入门竞赛经典》第 177 页 2017-3-10 10 还能不能更快... ?这样做依旧会超时, k的最大值是 100000000 让我们先来观察几组数剧后再来讨论
全文预览
