Browse Tag

数论

POJ 2635 The Embarrassed Cryptographer (同余问题)

已知K是两个素数的乘积，判断这两个素数中最小的一个是否小于L，若小于，输出BAD + MIN_PRIME，否则输出GOOD。

群 G 中任意一个元素 a ，都在 G 中有唯一的逆元 a‘

具有性质 a×a’=a’×a=e ，其中 e 为该群的单位元

对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数

必然存在整数对 x，y ，使得 gcd（a，b）=ax+by

要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。

Alex发明了一个有趣的游戏.，一开始他在黑板上写了n个正整数，然后他开始重复进行如下的操作：

1. 他选择黑板上三个数字a, b和c，把他们从黑板上擦掉。
2. 他从这三个数a, b和c中选择了两个数，并计算出他们的最大公约数，记这个数为d (d 可以是gcd(a,b)，gcd(a,c)或者gcd(b,c))。
3. 他在黑板上写下两次数字d。

显然，在操作n−2次后，黑板上只会留下两个相同的数字， Alex想要知道哪些数字可以最终留在黑板上。

给定数 n ，求出大于等于 n 的最小的丑数。