牛客练习赛44----D-小y的盒子

首先发出题目链接：
链接：https://ac.nowcoder.com/acm/contest/634/D
来源：牛客网
涉及：欧拉定理，快速幂

---

题目如下：


我去，题目又有求和，又是大数，果断放弃

---

对于这个题目，首先需要一些数学思考

小y有两组图片
第一组（蓝色）：1 3 9 27 81…（3^n-1）
第一组（红色）：1 3 9 27 81…（3^n-1）

可惜所有卡片混乱在一起，在这些混乱的卡片中每个3^n-1都有两张卡片

每个3^n-1可以化为3进制的数字

比如1(1),3(10),9(100),81(10000)…

所有卡片数字的总和m即为22222222222…2222（一共n个2）
（证明：3^n-1前n项和化为3进制为11111111（一共n个1），回合卡片中每个数字都有红色和蓝色两张卡片，所以m等于3^n-1前n项和的2倍）

现在的问题是组合卡片，求使得卡片和为1到m的所有卡片组合方案的和

---

从1到m每一个数字的都可以化为三进制数字h，每一个三进制数字h都有n位（不足n位补0）

然后考虑三进制数h每一位上面的数字（0,1,2）：
当第i位上的数字为1时，表示这一位上需要1张3^i-1数字的卡片（有且只有“红色”和“蓝色”两种选择）；
当第i位上的数字为2时，表示这一位上需要2张3^i-1数字的卡片（有且只有“红色和蓝色都要”这一种选择）；
当第i位上的数字为0时，表示这一位上不需要3^i-1数字的卡片（有且只有“不需要卡片”这一种选择）；
（ps：此时有人会说当第i位上的数字不为0时，不能由多张3^j(j<i-1)的卡片加起来得到吗？
然而，当第i位数字不为1时，你把3^j(j<i-1)所有卡片加起来也凑不齐第i位的数字）

这个三进制数h的n个位置上的每一位数字都有可能是1,2或者3。为1时，会有两种选择；为2或者0时，会有一种选择。

假设有i个位置是1，j个位置是2，n-i-j个位置是0

则当n=n₀时，所有的选择为
$\sum^{n_{0}}_{i}(C^{i}_{n_{0}}*2^{i}*\sum^{n_{0}-i}_{j}({C^{j}_{n-i}*1^{j}*C^{n_{0}-i-j}_{n_{0}-i-j}*1^{n_{0}-i-j})})$∑in0​​(Cn0​i​∗2i∗∑jn0​−i​(Cn−ij​∗1j∗Cn0​−i−jn0​−i−j​∗1n0​−i−j))
=$\sum^{n_{0}}_{i}(C^{i}_{n_{0}}*2^{i}*\sum^{n_{0}-i}_{j}{C^{j}_{n_{0}-i}})$∑in0​​(Cn0​i​∗2i∗∑jn0​−i​Cn0​−ij​)
=$\sum^{n_{0}}_{i}(C^{i}_{n_{0}}*2^{i}*2^{n_{0}-i})$∑in0​​(Cn0​i​∗2i∗2n0​−i)
=$\sum^{n_{0}}_{i}(C^{i}_{n_{0}}*2^{n_{0}})$∑in0​​(Cn0​i​∗2n0​)
=$2^{n_{0}}*\sum^{n_{0}}_{i}C^{i}_{n_{0}}$2n0​∗∑in0​​Cn0​i​
=$4^{n_{0}}$4n0​
$(ps:\sum^{n}_{i}C^{i}_{n}=2^{n})$(ps:∑in​Cni​=2n)

然后n不等于0，所以结果还要减去1，然后对p求余，于是所有的方案和为
$(4^{n}-1)　mod　p　(ps:1\le n\le10^{100000})$(4n−1)　mod　p　(ps:1≤n≤10100000)

---

对公式变形：
$(4^{n}-1)　mod　p=((4^{n}　mod　p)-1+p)　mod　p$(4n−1)　mod　p=((4n　mod　p)−1+p)　mod　p

由于n非常大，根据扩展欧拉定理可知
$4^{n}　mod　p=4^{((n　mod　\phi(p))+\phi(p))}　mod　p$4n　mod　p=4((n　mod　ϕ(p))+ϕ(p))　mod　p

（ps：$\phi(p)$ϕ(p)是欧拉函数，$\phi(p)$ϕ(p)的值为1~p中与p不互质的数的个数，求欧拉函数$\phi(p)$ϕ(p)是有公式的，不知道欧拉函数和欧拉定理可以看看其他我的博客）
通过公式求欧拉函数$\phi(p)$ϕ(p)值的代码如下
注意把(1-1.0/i)值化为浮点类型，如果是整型就错了，后来再化成long long类型

ll getDivisor(){
	ll sum=p;
	int i;
	ll p1=p;
	for(i=2;i*i<=p1;i++){
		if(p1%i==0)	sum=ll1*sum*(1-1.0/i);
		while(p1%i==0)	p1=p1/i;
	}
	if(p1!=1)	sum=ll1*sum*(1-1.0/p1);
	return sum;//sum为欧拉函数的值
}

所以现在只用通过大数求模的方式求出$(n　mod　\phi(p))$(n　mod　ϕ(p))，得到$((n　mod　\phi(p))+\phi(p))$((n　mod　ϕ(p))+ϕ(p))之后用快速幂求$(4^{((n　mod　\phi(p))+\phi(p))}　mod　p)$(4((n　mod　ϕ(p))+ϕ(p))　mod　p)，关于大数求模可以看看其他博客。
通过大数求模得到$((n　mod　\phi(p))+\phi(p))$((n　mod　ϕ(p))+ϕ(p))的值

ll getPow(){
	stream<<str;//stream为stringstream类型
	ll sum=0;
	char c;
	while(stream>>c)
		sum=(10*sum+c-'0')%divisor;
	stream.clear();
	return sum+divisor;//其中sum为n对欧拉函数求余的值，divisor是欧拉函数的值
}

然后是快速幂的代码

ll qSort(){
	ll x=4,sum=1;
	while(pow1!=0){
		if(pow1%2!=0)	sum=sum*x%p;
		pow1=pow1>>1;
		x=x*x%p;
	}
	return sum-1+p;//sum是4的n次方的值(sum-1+p)对p取余即为答案
}

---

举个例子

当n=13,p=15
p的质因子为2和3和5，则$\phi(p)=p*(1-1/2)*(1-1/3)*(1-1/5)=4$ϕ(p)=p∗(1−1/2)∗(1−1/3)∗(1−1/5)=4
$(n　mod　\phi(p))+\phi(p)=5$(n　mod　ϕ(p))+ϕ(p)=5
$4^{((n　mod　\phi(p))+\phi(p))}　mod　p=4$4((n　mod　ϕ(p))+ϕ(p))　mod　p=4
即答案为4（例子很简单，只要你实现了大数取模就可以）

---

代码如下：

#include <iostream>
#include <algorithm> 
#include <string>
#include <sstream>
#define ll1 (ll)1
using namespace std;
typedef long long ll;
stringstream stream;
ll p,divisor,pow1; 
string str;
int t;
ll qSort(){
	ll x=4,sum=1;
	while(pow1!=0){
		if(pow1%2!=0)	sum=sum*x%p;
		pow1=pow1>>1;
		x=x*x%p;
	}
	return sum-1+p;
}
ll getPow(){
	stream<<str;
	ll sum=0;
	char c;
	while(stream>>c)
		sum=(10*sum+c-'0')%divisor;
	stream.clear();
	return sum+divisor;
}
ll getDivisor(){
	ll sum=p;
	int i;
	ll p1=p;
	for(i=2;i*i<=p1;i++){
		if(p1%i==0)	sum=ll1*sum*(1-1.0/i);
		while(p1%i==0)	p1=p1/i;
	}
	if(p1!=1)	sum=ll1*sum*(1-1.0/p1);
	return sum;
}
int main(){
	cin>>t;
	while(t--){
		cin>>str>>p;
		divisor=getDivisor();
		pow1=getPow();
		cout<<qSort()%p<<endl;
	}
	return 0;
}