uva 数学课题入门

uva 数学专题入门

uva 11388 - GCD LCM链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2383描述：输入两个整数G，L [1, 2^31]，找出两个正整数a和b，使得二者最大公约数为G，最小公倍数为L。若有多解，输出a<=b且a最小的解。无解输出-1.思路：设a=n1*G, b=n2*G, (n1,n2>=1)因为a*b=G*L, 代入得n1*n2*G=L,所以L是G的倍数，若L%G != 0,无解。否则只要n1=1可以让a最小，所以b就等于L。

 K   N123 1123 2136 31410 
#include <iostream>#include <cstdio>#include <cstring>const int MOD = 1000000, M = 110;int c[M][M];void init(){memset(c, 0, sizeof(c));for (int i = 1; i < M; ++i)c[i][1] = 1, c[1][i] = i;for (int i = 2; i < M; ++i)for (int j = 2; j < M; ++j)c[i][j] = (c[i][j-1] + c[i-1][j]) % MOD;}int main(){int n, k;init();while (scanf("%d %d", &n, &k) && n && k){printf("%d\n", c[n][k]);}return 0;}