实验4高程 gcd和ex_gcd

1. (程序题)最大公约数和最小公倍数

请计算2个数的最大公约数和最小公倍数；（最大公约数可以使用辗转相除法，最小公倍数=2个数的乘积/它们的最大公约数；）

输入数据有多组，每组2个正整数a,b(2<=a,b<=1000),在一行内输出a和b的最大公约数和最小公倍数.

Sample Input

10 15

Sample Output

5 30

Hint

#include <iostream>
using namespace std;
int gcd(int a,int b)
{if(b==0)return a;return gcd(b,a%b);
}
int main()
{int a,b,num,ans;cin>>a>>b;num=gcd(a,b);ans=a*b/num;cout<<num<<" "<<ans<<endl;return 0;
}

2. (程序题)多个数的最大公约数

给定n(n<=10)个正整数，你的任务就是求它们的最大公约数，所有数据的范围均在long long内。

Input

输入数据有多组，每组2行，第一行为n，表示要输入数字的个数，接下来第二行有n个正整数。

Output

输出一个数，即这n个数的最大公约数。

Sample Input

5

2 4 6 8 10

2

13 26

Sample Output

2

13

#include <iostream>
using namespace std;
long long gcd(long long a,long long b)
{if(b==0)return a;return gcd(b,a%b);
}
int main()
{long long b,a;int n,s[15],i,ans;while(cin>>n){ans=0;for(i=1;i<=n;i++){cin>>s[i];}for(i=1;i<n;i++){ans=gcd(ans,s[i]);}cout<<ans<<endl;}return 0;
}

3. (程序题)
同余方程

求关于 x的同余方程 ax≡1(mod b) 的最小正整数解。

Input

一行，包含两个正整数 a,b用一个空格隔开。

Output

一个正整数 x ，即最小正整数解。输入数据保证一定有解。

Sample Input

3 10

Sample Output

7

#include <iostream>
using namespace std;
void ex_gcd(int a,int b,int &x,int &y)
{if(b==0){x=1;y=0;return;}ex_gcd(b,a%b,x,y);int t=x;x=y;y=t-(a/b)*y;//
}
int main()
{int a,b,x,y;cin>>a>>b;ex_gcd(a,b,x,y);x=(x+b)%b;cout<<x<<endl;return 0;
}

4. (程序题)

昨日重现

兴安黑熊在高中学习数学时，曾经知道这样一个公式：f(n)=1^2+2^2+3^2+.......+n^2,这个公式是可以化简的，化简后的结果是啥它却忘记了，也许刚上大二的你能记得。现在的问题是想要计算f(n)对1007取余的值，你能帮帮他吗？

Input

输入数据有多组（不超过100组），每组一个数n. (1<=n <=1,000,000,000).

Output

输出f(n)对1007取余的值。

Sample Input

3

4

100

Sample Output

14

30

1005

#include <iostream>
using namespace std;
void ex_gcd(long long  a,long long  b,long long  &x,long long  &y)
{if(b==0){x=1;y=0;return;}ex_gcd(b,a%b,x,y);int t=x;x=y;y=t-(a/b)*y;
}
int main()
{long long a,b,ans,x,y,n;while(cin>>n){ex_gcd(6,1007,x,y);x=(x+1007)%1007;ans=(n*(n+1))%1007;ans=(ans*(2*n+1))%1007;ans=(ans*x)%1007;cout<<ans<<endl;}return 0;
}