6.cpp

7道ACM题

#include <stdio.h>


/* 
 * 根据表达式: f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7. 
 * 可以得出: f(n) = ( ( (A * f(n - 1)) mod 7 ) + ( (B * f(n - 2)) mod 7 ) ) mod 7.
 * 也就是说,当  B mod 7 == 0 时, f(n) 退化成: f(n) = A * f(n - 1) mod 7. 这时候可以用"幂取余"算法简单求解.
 * 当 B mod 7 != 0, 我们可以通过求出结果的循环的周期来缩短时间.
 */

int main()
{
	// 求 a^b % n 值,用分治算法,当 b 很大时为 O( logn ).
	int modExp( int a, int b, int n );

	int i;
	int A, B, n;
	int m = 1;
	int f1 = 1, f2 = 1, temp;
	int flag;

	scanf( "%d%d%d", &A, &B, &n );	

	while ( A != 0 || B != 0 || n != 0 )
	{
		// 退化成"幂求余",直接利用函数求解
		if ( B % 7 == 0 )
		{
			printf( "%d\n", modExp( A, n - 2, 7 ) );
		}
		else
		{
			f1 = 1, f2 = 1, temp;
			temp = ( A * f1 + B * f2 ) % 7;
			f2 = f1, f1 = temp;

			// 利用 m 的值来算出结果循环的周期
			m = 1;		
			while ( f1 != 1 || f2 != 1 )
			{
				temp = ( A * f1 + B * f2 ) % 7;
				f2 = f1;
				f1 = temp;
				m++;
			}
 
			n %= m;
			if ( n == 0 )
				n = m;

			// 因为前两次已经是 f(1) 和 f(2),所以在这里得把周期减去 2
			f1 = 1, f2 = 1;
			for ( i = 1; i <= n - 2; i++ )
			{
				temp = ( A * f1 + B * f2 ) % 7;
				f2 = f1;
				f1 = temp;
			}

			printf( "%d\n", f1 );
		}

		scanf( "%d%d%d", &A, &B, &n );	
	}

	return 0;
}


// 该方法利用了数学定理: a * a % b == ((a % b) * (a % b)) % b
// 比如: a^8 % n, 这个算式可以等份为 (a^4 % n) * (a^4 % n) % n,也就是说可以把一个大数分成两部分,先把它们各自模除之后再合并
// 这就可以用分治递归的算法在 O( logn ) 的时间复杂度内得出解
int modExp( int a, int b, int n )
{
	int t, y;
	t = 1, y = a;

	while ( b != 0 )
	{
		if ( b % 2 == 1 )
			t = t * y % n;
		y = y * y % n;
		b = b / 2;
	}

	return t;
}