第六周测验

深碍√TFBOYSˉ_ 2022-05-20 09:57 258阅读 0赞

## 1788:Pell数列 [http://noi.openjudge.cn/ch0202/1788/][http_noi.openjudge.cn_ch0202_1788] ##

描述

Pell数列a1, a2, a3, ...的定义是这样的，a1 = 1, a2 = 2, ... , an = 2 \* an − 1 + an - 2 (n > 2)。  
给出一个正整数k，要求Pell数列的第k项模上32767是多少。

输入

第1行是测试数据的组数n，后面跟着n行输入。每组测试数据占1行，包括一个正整数k (1 ≤ k < 1000000)。

输出

n行，每行输出对应一个输入。输出应是一个非负整数。

样例输入

2
    1
    8

样例输出

1
    408

#include<iostream>
    #define MAXN 1000010
    int a[MAXN];
    using namespace std; 
    int main()
    {
    	int n, k;
    	cin >> n;
    	a[1] = 1;
    	a[2] = 2;
    	while(n -- )
    	{
    		cin >> k;
    		if(k == 1) cout << "1" << endl;
    		else if(k == 2) cout << "2" << endl;
    		else
    		{
    			for(int i = 3; i <= k; ++i)
    			{
    				a[i] = (2*a[i-1] + a[i-2]) % 32767;
    			}
    			cout << a[k] << endl;
    		}
    	}
    	return 0;
    }

## 7592:求最大公约数问题 [http://noi.openjudge.cn/ch0202/7592/][http_noi.openjudge.cn_ch0202_7592] ##

描述

给定两个正整数，求它们的最大公约数。

输入

输入一行，包含两个正整数(<1,000,000,000)。

输出

输出一个正整数，即这两个正整数的最大公约数。

样例输入

6 9

样例输出

提示

求最大公约数可以使用辗转相除法：  
假设a > b > 0，那么a和b的最大公约数等于b和a%b的最大公约数，然后把b和a%b作为新一轮的输入。  
由于这个过程会一直递减，直到a%b等于0的时候，b的值就是所要求的最大公约数。  
比如：  
9和6的最大公约数等于6和9%6=3的最大公约数。  
由于6%3==0，所以最大公约数为3。

#include<iostream>
    using namespace std;
    int gcd(int a, int b)
    {
    	if(a % b == 0) 
    		return b;
    	else return gcd(b, a%b);
    }
    int main()
    {
    	long long a, b;
    	cin >> a >> b;
    	if(a < b) 
    	{
    		a = a ^ b;
    		b = b ^ a;
    		a = a ^ b;
    	}
    	cout << gcd(a,b) << endl;
    	return 0; 
    }

【注意】当不要a与b交换这一步代码也是对的。

因为在调用gcd（a,b）函数时：

(1) a = 6, b = 9;
    
    (2) a = b = 9; b = a % b = 6 % 9 = 6.会自动将数据交换过来。

其余的题没找到出处~

[http_noi.openjudge.cn_ch0202_1788]: http://noi.openjudge.cn/ch0202/1788/
[http_noi.openjudge.cn_ch0202_7592]: http://noi.openjudge.cn/ch0202/7592/