此题乃师兄[ 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;
}
- 大小: 8.2 KB
- 大小: 3.3 KB