高次幂取模的应用

此题乃师兄[ TT_last ]原创题！Orz膜拜一下

a simple problem

Problem Description
As we know , to caculate the sum ofis hard if the n is large,because today is Valentines Day,to make this problem more easy ,you only need to caculate the sum mod c

Input
There are multiply testcases. Each testcase, there is one line contains two integers n,c;(1<=n <= 10^1000000,1<=c <=1000000000

Output
For each testcase, output an integer, denotes the result of the sum mod c

Sample Input
2 4
3 5

Sample Output
0
2

Author
TT_last


计算这个的公式： n*2^(n-1)

高次取模降幂公式：

Phi是欧拉函数

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define L long long
#define inf 0x3fffffff

char s[2000005];

L qmod (L a, L b, L c)    //快速幂取模
{
	L k = 0, i, d[40], res = 1;
	while (b)
		d[k++] = b % 2, b >>= 1;
	for (i = k - 1; i >= 0; i--)
	{
		res = res * res % c;
		if (d[i] == 1)
			res = res * a % c;
	}
	return res;
}

L Euler (L n)    //求欧拉函数值
{
	L i, res = n;
	for (i = 2; i * i <= n; i++)
	{
		if (n % i == 0)
		{
			n /= i, res = res - res/i;
			while (n % i == 0)
				n /= i;
		}
	}
	if (n > 1)
		res = res - res/n;
	return res;
}

int main()
{
	L tp, c, len, n, k1, k2, i, phi, res;
	while (~scanf ("%s%lld", s, &c))
	{
		len = strlen (s);
		tp = 0;
		for (i = 0; i < len; i++)
		{
			tp *= 10;
			tp += s[i] - '0';
			if (tp >= c)
				tp %= c;
		}
		k1 = tp;    //k1是n%c
		i = 1;
		while (s[len-i] == '0')    //n变成n-1
			s[len-i] = '9', i++;
		s[len-i]--;
		phi = Euler (c);
		n = -1;
		if (len < 11)
			sscanf (s, "%lld", &n);
		if (n == -1 || n >= phi)    //用降幂公式的条件
		{
			tp = 0;
			for (i = 0; i < len; i++)
			{
				tp *= 10;
				tp += s[i] - '0';
				if (tp >= phi)
					tp %= phi;
			}
			tp += phi;
		}
		else tp = n;
		k2 = qmod (2, tp, c);    //k2是2^(n-1)%c，其中n-1已降幂
		res = k1 * k2 % c;    //相当于(n%c*2^(n-1)%c)%c
		printf ("%lld\n", res);
	}
    return 0;
}

评论

2 楼 基德KID.1412 2011-08-08  

sgeteternal 写道

原来有高次降幂！甘样确实唔会超时鸟 爽！

1 楼 sgeteternal 2011-08-08  

原来有高次降幂！甘样确实唔会超时鸟 爽！