欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

ACM-ICPC 2018 焦作赛区网络预赛 - G Give Candies - 规律+欧拉降幂

程序员文章站 2022-03-12 15:28:16
...

ACM-ICPC 2018 焦作赛区网络预赛 - G Give Candies - 规律+欧拉降幂

ACM-ICPC 2018 焦作赛区网络预赛 - G Give Candies - 规律+欧拉降幂 

思路:

找规律可以知道是2^(n-1)

n的范围很大,所以用欧拉降幂公式降幂:ACM-ICPC 2018 焦作赛区网络预赛 - G Give Candies - 规律+欧拉降幂

欧拉φ函数:在数论中,对正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为φ函数、欧拉商数等。φ(1)=1

m=1e9+7是个质数,所以φ(1e9+7)=1e9+6

给质数降幂后就愉快地用快速幂求解好了~

代码如下:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<string>
#include<cstring>
using namespace std;
#define ll long long
const int mod=1e9+7,md=1e9+6;

ll mod_pow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}

int main(){
    int t;
    scanf("%d",&t);
    string s;
    while(t--){
        cin>>s;
        ll mi=0;
        for(int i=0;i<s.length();i++){
            mi=(mi*10+s[i]-'0')%md;
        }
        mi=(mi-1+md)%md;
        printf("%lld\n",mod_pow(2,mi));
    }
}