美文网首页
欧拉函数 || 降幂

欧拉函数 || 降幂

作者: Vincy_ivy | 来源:发表于2020-02-11 11:34 被阅读0次

https://zybuluo.com/Junlier/note/1300214
https://kvxi.org/2019/02/18/60847a3/

欧拉函数

φ[p]是欧拉函数,表示0到x中与x互质的数的个数

引理(对于素数p)
通式:φ(x)=x*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn)
其中p1, p2……pn为x的所有质因数,x是不为0的整数。φ(1)=1(唯一和1互质的数就是1本身)。

例如φ(24)=8,因为1, 5, 7, 11, 13, 17, 19, 23均和 24 互质。
φ(24)=24*(1-1/2)*(1-1/3)=8.
其中(p1.....pn)为N的素因子.
对于质数p,φ(p) = p - 1,注意φ(1)=1.

欧拉函数是积性函数——

若m,n互质,φ(mn)=φ(m)φ(n)。

若n是质数p的k次幂,φ(n)=pk-p(k-1)=(p-1)p^(k-1),因为除了p的倍数外,其他数都跟n互质。

特殊性质:当n为奇数时,φ(2n)=φ(n)

欧拉函数还有这样的性质:
设a为N的质因数,若(N % a == 0 && (N / a) % a == 0) 则有E(N)=E(N / a) * a;若(N % a == 0 && (N / a) % a != 0) 则有:E(N) = E(N / a) * (a - 1)。

模板

int n,m;
int phi(int n){
    int res=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            res=res-res/i;//不能是res*(1-1/i);
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)
        res=res-res/n;
    return res;
} 

int main(){
    cin>>n;
    m=phi(n);
    cout<<m;
    return 0;
} 

 

欧拉降幂

欧拉定理:若a与m互质,则a^f(m)恒等于1(mod m)
降幂公式:a^b mod c = a^(b mod phi(c)+phi(c)) mod c。{phi(c) == f(c)}


模板

#define ll long long 
ll n,p,ans,m;
int phi(int n){
    int res=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            res=res-res/i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n>1)
        res=res-res/n;
    return res;
} 

ll quicksort(ll x,ll y, ll p){
    ll ans=1;
    ll a=x;
    while(y){
        if(y&1)
            ans=(ans*a)%p;
        a=(a*a)%p;
        y>>=1;
    }
    return ans;
}

ll f(ll p){
    if(p==1)
        return 0;
    ll k=phi(p);
    return quicksort(f(k)+k,p);
}

int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>p;
        m=phi(p);
        ans=f(p);
        cout<<ans;
    }
    return 0;
} 

 

模板题目:

2的n次方MOD1e9+7(1<=n<=10100000)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <sstream>
using namespace std;
#define ll long long 
ll p=1000000007,ans,b,mod;
char n[1000006],m[1000006]; 
//欧拉函数 
int phi(ll n){
    int res=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            res=res-res/i;
            while(n%i==0)
                n/=i;
        } 
    }
    if(n>1)
        res=res-res/n;
    return res;
}

ll quicksort(ll x,ll y,ll p){
    ll ans=1,base=x%p;
    while(y){
        if(y&1)
            ans=(ans*base)%p;
        base=(base*base)%p;
        y>>=1;
    }
    return ans;
}
/*
ll f(ll p){
    if(p==1)
        return 0;
    ll k=phi(p);
    return quicksort(f(k)+k,p);
}*/


int main(){
    scanf("%s",n);
    int phi_p=phi(p);
    int len=strlen(n);
    ll sum=0;
    for(int i=0;i<len;i++){
        sum=(sum*10+n[i]-'0')%phi_p;
    }
    cout<<quicksort(2,sum+phi_p,p)<<endl;
    return 0;
}

 

SCNU 1240 幼稚园

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <sstream>
using namespace std;
#define ll long long 
ll n,p=1000000007,ans,m,b,mod;
string s;

ll quicksort(ll x,ll y){
    ll ans=1,a=x;
    while(y){
        if(y&1)
            ans=(ans*a)%p;
        a=(a*a)%p;
        y>>=1;
    }
    return ans;
}

int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>s;
        ans=0,b=0,mod=phi(p);
        for(int i=0;i<s.size();i++)
            b=(b*10+s[i]-'0')%(p-1);
        b=(b-1+p-1)%(p-1);
        ans=quicksort(2,b);
        cout<<ans<<endl;
    }
    return 0;
}

A. Ternary String 牛客网暑期ACM多校训练营(第四场)——规律+欧拉

题目

A ternary string is a sequence of digits, where each digit is either 0, 1, or 2.
Chiaki has a ternary string s which can self-reproduce. Every second, a digit 0 is inserted after every 1 in the
string, and then a digit 1 is inserted after every 2 in the string, and finally the first character will disappear.
For example, 212'' will become11021'' after one second, and become ``01002110'' after another
second.
Chiaki would like to know the number of seconds needed until the string become an empty string. As the
answer could be very large, she only needs the answer modulo (109 + 7).

输入描述

There are multiple test cases. The first line of input is an integer T indicates the number of test cases. For
each test case:
The first line contains a ternary string s (1 ≤ |s| ≤ 10 5).
It is guaranteed that the sum of all |s| does not exceed 2 x 10 6.

输出描述

For each test case, output an integer denoting the answer. If the string never becomes empty, output -1
instead.

输入

3
000
012
22

输出

3
93
45

题意:给你一个字符串,由0,1,2组成,每秒钟在1后面添加一个0,在二后面添加一个1,然后去掉字符串的首个字符,问需要多少秒后,字符串变成空串。
1
01
001
0001
00001
000001
0000001
00000001
000000001
0000000001
相对应的答案是:2,4,6,8,10,12,14,16,18,20
2
02
002
0002
00002
000002
0000002
00000002
000000002
0000000002
相对应的答案是:3,9,21,45,93,189,381,765,1533,3069
然后可以推出,0的时候,t'=t+1;1的时候,t'=2*(t+1);2的时候, t'=3*(2^(t+1)-1)
但是我们现在知道的就只有以下四种方式

  • 1、( a + b ) % n = ( a%n + b%n ) % n

  • 2、( a - b ) % n = ( a%n - b%n ) % n

  • 3、( a * b ) % n = ( a%n * b%n ) % n

  • 4、( a ^ b ) % n = ( (a%n) ^ b ) % n
    所以对于 t'=3*(2^(t+1)-1),我们要进行欧拉降幂
    这道题要用到dfs

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <sstream>
using namespace std;
#define ll long long 
ll n,p=1000000007,ans,m,b,mod;
string s;
//欧拉函数 
int phi(ll n){
    int res=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0){
            res=res-res/i;
            while(n%i==0)
                n/=i;
        } 
    }
    if(n>1)
        res=res-res/n;
    return res;
}

ll quicksort(ll x,ll y,ll p){
    ll ans=1,base=x%p;
    while(y){
        if(y&1)
            ans=(ans*base)%p;
        base=(base*base)%p;
        y>>=1;
    }
    return ans;
}

ll f(ll p){
    if(p==1)
        return 0;
    ll k=phi(p);
    return quicksort(f(k)+k,p);
}


int main(){
    int t;
    cin>>t;
    while(t--){
        ans=0;
        cin>>s;
        for(int i=0;i<s.size();i++){
            if(s[i]=='0')
                ans+=1;
            else if(s[i]=='1')
                ans=2*(ans+1);
            else
                ans=3*(f(ans)-1);
        }
    }
    return 0;
}

相关文章

  • 欧拉函数 || 降幂

    https://zybuluo.com/Junlier/note/1300214https://kvxi.org/...

  • super_log(欧拉降幂)

    super_log题意:根据题面可以推出一个公式其中的个数是,输出思路:欧拉降幂(广义欧拉定理)=其中 结构1 结...

  • Codeforce-Power Tower(欧拉降幂)

    Power Tower题意:一个序列有个数,次询问,将到这个区间的数叠起来模上思路:欧拉降幂

  • 欧拉函数

    欧拉函数介绍 欧拉函数是小于x的整数中与x互质的数的个数,一般用φ(x)表示。特殊的,φ(1)=1。 求欧拉函数

  • 数论四大定理之欧拉定理

    本文分为两个部分,第一部分介绍欧拉定理的证明,第二部分介绍欧拉函数的求法。 欧拉函数 欧拉函数是小于等于 n 的正...

  • 大数幂模---欧拉降幂/java/Python

    2019牛客网寒训4场#E 题目描述 精通程序设计的 Applese 叕写了一个游戏。在这个游戏中,有一个 n 行...

  • 关于RSA的学习整理

    一、RSA原始模型整理 1. 基础理论:欧拉函数与欧拉定理 欧拉函数:,表示[1,n)中与n互素的数的个数。显然若...

  • 欧拉函数

    欧拉函数:euler(n)为小于n的数中与n互质的数的个数; 根据需要分为:单数查询,范围查询 我们可以发现,单数...

  • 欧拉函数

    欧拉函数 定义:若则称a,b互质。gcd(a,b,c)称为a,b,c互质,而称为两两互质。例如2,3,4互质但是不...

  • 欧拉定理

    欧拉函数欧拉函数是小于等于 的正整数中与 互质的数的个数。 欧拉定理对于任意互素的 和 ,有参考链接费马小定理...

网友评论

      本文标题:欧拉函数 || 降幂

      本文链接:https://www.haomeiwen.com/subject/kbjmkctx.html