jzoj100027. 【NOIP2017提高A组模拟7.7】表达式

Description

Input

一行两个整数k，p。

Output

一行一个整数表示答案。

Sample Input

1 3

Sample Output

6

Data Constraint

对于20%的数据：$k*p<=10^5$
对于另外20%的数据 $k=1$
对于70%的数据：$k*p<=10^9$
对于100%的数据：$k,p<=10^9$

题解

这题一看就是一道不友好的题。
前%40暴力+打表
%70题解说：发挥人类智慧。
然而并不会做
%100
解法一：简单自然的找规律，可以发现一些周期或是别的神奇的东东。
解法二：推式子。
我们看到题目要求：
$sum_{i=1}^{k*p}i^{2*p-1} mod p^2$
放在前面：我们要推一个前置知识。
二项式展开：
$(a+b)^n=sum_{i=0}^{n}C_{n}^{i}*a^{n-i}*b^i$

然后我们要证明：
$sum_{i=1}^{p-1}i^{2p-1}equiv p(p+1)/2(mod p^2)$
过程：
$sum_{i=1}^{p-1}i^{2p-1}+sum_{i=1}^{p-1}i^{2p-1}equiv p(p+1)(modp^2)$

$sum_{i=1}^{p-1}i^{2p-1}+sum_{i=1}^{p-1}{(p-i)}^{2p-1}equiv p(p+1)(modp^2)$

$sum_{i=1}^{p-1}{i}^{2p-1}+{(p-i)}^{2p-1}equiv p(p+1)(modp^2)$

$sum_{i=1}^{p-1}{i}^{2*p-1}-sum_{j=0}^{2p-1}C_{2p-1}^j*(-i)^{2p-1-j}*p^{j}equiv p(p+1)(modp^2)$

由于当j>=2时，后面的式子是没有用的“$sum_{j=0}^{2p-1}C_{2p-1}^j*(-i)^{2p-1-j}*p^{j}$”（模意义下）
所以设后面的式子值为：S
当j=0时$S=-1*1*i^{2p-1}$
当j=1时$S=(2p-1)*i^{2p-2}*p$
得到：
$sum_{i=1}^{p-1}{i}^{2p-1}-i^{2p-1}+(2p-1)*p*i^{2p-2}equiv p(p+1)(modp^2)$

$sum_{i=1}^{p-1}(2p-1)*p*i^{2p-2}equiv p(p+1)(modp^2)$

$sum_{i=1}^{p-1}(2p-1)*i^{2p-2}equiv p+1(modp)$（由于两边同时除p，模数也要除p）

因为费马小定理：$a^{p-1}equiv 1 (mod p)(p为质数)$

所以$i^{2p-2}=i^{2(p-1)}={(i^2)}^{p-1}equiv 1(modp)$

所以原来就变成了：
$sum_{i=1}^{p-1}2p-1equiv p+1(modp)$

$(p-1)(2p-1)equiv p+1(mod p)$（去掉西格玛）

$2p^2-4p+1equiv 1(mod p)$（拆出来）
由于是模p意义下，所以变成了：$1equiv1(mod p)$
得证。
那么回到题目：
$sum_{i=1}^{kp}i^{2p-1} mod p^2$

$sum_{i=1}^{k}sum_{j=1}^{p}[(i-1)*p+j]^{2p-1} mod p^2$（拆开西格玛）
我们发现，可以把(i-1)在前面西格玛替换一下，而且由于j=p时，$modp^2$为0
所以变成：
$sum_{i=0}^{k-1}sum_{j=1}^{p-1}(i*p+j)^{2p-1} mod p^2$
熟悉的二项式展开：
$sum_{i=0}^{k-1}sum_{j=1}^{p-1}[j^{2p-1}+(2p-1)*i*p*j^{2p-2}] mod p^2$
整理一下：
$sum_{i=0}^{k-1}sum_{j=1}^{p-1}j^{2p-1}+sum_{i=0}^{k-1}*i*sum_{j=1}^{p-1}(2p-1)*j^{2p-2}*p (mod p^2)$
左边可以根据上面证明：得$sum_{i=0}^{k-1}p(p+1)/2=kp(p+1)/2$
右边可以根据上面证明过程中的结论化简，得：
$sum_{i=0}^{k-1}*i*p*(p+1)=k*(k-1)*p*(p+1)/2$
那么答案就是：$kp(p+1)/2+k*(k-1)*p*(p+1)/2( mod p^2)$
化简：$k^2*p*(p+1)/2(mod p^2)$
用快（gui）速乘解决即可。

var
        i,j,k,l,n,m:longint;
        p,q,ans,answer,mo:int64;
function tsm(a,b:int64):int64;
var
        i,j,k,l:int64;
begin
        l:=0;
        while b>0 do
        begin
                if b and 1>0 then l:=(l+a) mod mo;
                b:=b div 2;
                a:=(a*2) mod mo;
        end;
        exit(l);
end;
begin
        readln(q,p);
        mo:=p*p;
        writeln(tsm(tsm(tsm(q,q),p),(p+1) div 2));
end.