ACM必做50题的解题-数论

由天下分享时间：2024/11/27 22:32:40 加入收藏我要投稿点赞

poj 1061 青蛙的约会

这题用的是解线性同余方程的方法，之前没接触到过，搜索资料后看到一个人的博客里面讲的很好就拷贝过来了。内容如下：

对于方程：ax≡b(mod m)，a，b，m都是整数，求解x 的值，这个就是线性同余方程。符号说明：

mod表示：取模运算

ax≡b(mod m)表示：(ax - b) mod m = 0，即同余 gcd(a,b)表示：a和b的最大公约数

求解ax≡b(mod n)的原理：对于方程ax≡b(mod n)，存在ax + by = gcd(a,b)，x，y是整数。而ax≡b(mod n)的解可以由x，y来堆砌。具体做法如下：

第一个问题：求解gcd(a,b)

定理一：gcd(a,b) = gcd(b,a mod b)

欧几里德算法

int Euclid(int a,int b) {

if(b == 0) return a; else

return Euclid(b,mod(a,b)); }

附：取模运算

int mod(int a,int b) {

if(a >= 0)

return a % b; else

return a % b + b; }

第二个问题：求解ax + by = gcd(a,b)

定理二：ax + by = gcd(a,b)= gcd(b,a mod b) = b * x' + (a mod b) * y'

= b * x' + (a - a / b * b) * y' = a * y' + b * (x' - a / b * y') = a * x + b * y 则：x = y'

y = x' - a / b * y'

以上内容转自hi.http://m.70edu.com//redcastle/blog/item/934b232dbc40d336349bf7e4.html

由这个可以得出扩展的欧几里德算法：

int exGcd(int a, int b, int &x, int &y) {

if(b == 0) {

x = 1; y = 0; return a; }

int r = exGcd(b, a % b, x, y); int t = x; x = y;

y = t - a / b * y; return r; }

代码：

#include #include #include #include

using namespace std;

__int64 mm,nn,xx,yy,l; __int64 c,d,x,y;

__int64 modd(__int64 a, __int64 b) {

if(a>=0) return a%b; else

return a%b+b; }

__int64 exGcd(__int64 a, __int64 b) {

if(b==0) { x=1; y=0;

return a; }

__int64 r=exGcd(b, a%b); __int64 t=x; x=y;

y=t-a/b*y; return r; }

int main() {

scanf(\ if(mm>nn) //分情况 {

d=exGcd(mm-nn,l); c=yy-xx; } else {

d=exGcd(nn-mm,l); c=xx-yy; }

if(c%d != 0) {

printf(\ return 0; }

l=l/d;

x=modd(x*c/d,l); ///取模函数要注意 printf(\

system(\ return 0; }

POJ 1142 SmithNumber

题意：寻找最接近而且大于给定的数字的SmithNumber

什么是SmithNumber？

用sum(int)表示一个int的各位的和，那一个数i如果是SmithNumber,则sum（i） =

sigma( sum(Pj )),Pj表示i的第j个质因数。例如4937775= 3*5*5*65837，4+9+3+7+7+7+5 = 42，3+5+5+（6+5+8+3+7） = 42，所以4937775是SmithNumber。

思路：要寻找大于给定数字且最接近给定数字的SmithNumber，只要将给定数字不断的加1，判断它是否是SmithNumber就行了，如果是SmithNumber就立即输出。

但是如何判断是否是SmithNumber呢？首先就是要对数字进行质因数分解。质因数分解要保证因子都是质数。这里先介绍一个如何判断一个数int是否是质数呢，如果对于这个数，i = 2.....sqrt(int)都不是它的约数，那int就是一个质数。所以我们可以将i初始化为2，然后不断递增i，看i是否是int的一个约数，如果是的话那i就是int的一个质因数（因为这个数是从2开始第一个可以整除int的数，它不可能是一个可以分解的合数，否则，它的约数在它之前就整除int），然后将int除以该质因数，重置i为2，重新对int判断它是否是质数。这样最后剩下的int一定是一个质数，从而对int进行了质因数分解

然后就很简单的将数字各质因数的各位加起来，看和是否等于该数字的各位和，如果相等那它可能就是SmithNumber，为什么说只是可能呢，因为这个数可能是质数，但是质数不是SmithNumber。

#include

#include int Sum( int number ) {

int sum = 0;

while( number != 0 ) {

sum += number % 10; number /= 10; }

return sum; }

bool SmithNumber( int number ) {

int i = 2;

int temp = number;

int sumOfNumber = Sum( number ); int sum = 0;

while( i <= (int)sqrt( (double)number ) ) {