牛客寒假算法基础集训营4 E. Applese涂颜色(思维+数论)
牛客寒假算法基础集训营4 E. Applese涂颜色(思维+数论)
Ch_Zaqdt
发布于 2019-03-01 17:33:01
发布于 2019-03-01 17:33:01
题目链接：https://ac.nowcoder.com/acm/contest/330/E
结论其实不难推出来，因为要求每一行的相邻的颜色不能一样，那么肯定就是黑白黑白这样交替，那么对于每一行来说都有两种方案，那么结果就是2^n，然而这道题的难点不是推结论，而是高精度，n和m的数据范围都是10^100000，这道题可以用欧拉降幂去写，首先欧拉定理是x^phi(y) ≡ 1(mod y)，phi是求y的欧拉值的，根据这一定理，就可以实现降幂的操作了。但是这道题中p是1e9+7，显然是个质数，所以根据欧拉函数的性质有质数的欧拉值为它本身减1，所以这里可以根据费马小定理直接对2^n化简得到2^(n%(p-1))，所以根据同余定理就可以求出n%(p-1)的值了，化简过程如下图。
然后根据同余定理就可以把n降为p-1以内的数了，然后再根据快速幂求得结果就好了。下面贴上两种code。
AC代码(费马小定理)：
#include<bits/stdc++.h>
#define ll long long
const int mod = 1e9 + 7;
using namespace std;
string n,m;
ll ppow(ll a, ll b){
ll sum = 1;
a %= mod;
while(b > 0){
if(b % 2 == 1) sum = (sum * a) % mod;
b /= 2;
a = (a * a) % mod;
}
return sum;
}
int main()
{
cin>>n>>m;
int len = n.length();
ll ans = 0;
for(int i=0;i<len;i++){
ans = (ans * 10 + (n[i] - '0')) % (mod - 1);
}
printf("%lld\n", ppow(2, ans));
return 0;
}AC代码(欧拉降幂)：
#include<bits/stdc++.h>
#define ll long long
const int mod = 1e9 + 7;
using namespace std;
string n,m;
ll ppow(ll a, ll b){
ll sum = 1;
a %= mod;
while(b > 0){
if(b % 2 == 1) sum = (sum * a) % mod;
b /= 2;
a = (a * a) % mod;
}
return sum;
}
ll phi(ll n){
ll res = n;
for(int i=2;i*i<=n;i++){
if(n % i == 0) res = res / i * (i - 1);
while(n % i == 0) n /= i;
}
if(n > 1) res = res / n * (n - 1);
return res;
}
int main()
{
cin>>n>>m;
int len = n.length();
ll ans = 0;
ll p = phi(mod);
for(int i=0;i<len;i++){
ans = (ans * 10 + (n[i] - '0')) % p;
}
printf("%lld\n", ppow(2, ans));
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019年01月30日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读