高次幂取模的应用

2019-04-13 14:31发布

站内文章 / 模拟电子
10158 0 1438
[b][size=medium][color=blue]此题乃师兄[ TT_last ]原创题！Orz膜拜一下[/color]

[align=center][color=green]a simple problem[/color][/align]
[color=blue]Problem Description[/color]
As we know , to caculate the sum of[img]http://dl.iteye.com/upload/attachment/531763/7269368e-96a6-3836-874b-6e43d1262fe8.jpg[/img]is 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

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

[color=blue]Output[/color]
For each testcase, output an integer, denotes the result of the sum mod c

[color=blue]Sample Input[/color]
2 4
3 5

[color=blue]Sample Output[/color]
0
2

[color=blue]Author[/color]
TT_last

[img]http://dl.iteye.com/upload/attachment/531763/7269368e-96a6-3836-874b-6e43d1262fe8.jpg[/img]
[color=blue]计算这个的公式： n*2^(n-1)[/color]

高次取模降幂公式：[img]http://dl.iteye.com/upload/attachment/531761/b2c93169-8323-37f9-8dda-4999cb233343.jpg[/img]

Phi是欧拉函数
[/size][/b]


#include
#include
#include
#include
#include
//#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 ", res);
}
return 0;
}

热门文章