指数循环节

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了指数循环节，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含4768字，纯文字阅读大概需要7分钟。

内容图文

$$求证a^b\equiv a^{b\%\varphi(m)+\varphi(m)}(\%m),其中b\geq \varphi(m)$$

我们模$m$最多只有$m$种结果，所以根据鸽巢原理，在

$$a^0,a^1,...,a^m(\%m)$$

这$m+1$个数中，一定存在最小的$r$和最小的$s$，满足$a^r\equiv a^{r+s}(\%m)$且$r+s\leq m.$$......(1)$

所以序列其实是这样的：

$$a^0,a^1,a^2,...,a^{r-1},a^r,a^{r+1},...,a^{r+s-1},a^r,a^{r+1},...(\%m)$$

也就是说，从$a^0$到$a^{r-1}$不是重复的，但是从$a^r$开始，会循环出现$a^r,a^{r+1},...,a^{r+s-1}$，循环节长度为$s$$......(2)$

由$(1)$式得：$m|a^{r+s}-a^{r}$，即$m|a^{r}(a^{s}-1)$

不妨设$m=a^{r0}m‘$，且$(a,m‘)=1$$......(3)$

变成$a^{r0}m‘|a^{r}(a^{s}-1)$$......(4)$

不妨设$r0<r$

则由$(4)$式得$m‘|a^{r-r0}(a^{s}-1)$，即$m‘|a^{r-r0+s}-a^{r-r0}$，所以$a^{r-r0}\equiv a^{r-r0+s}(\%m‘)$

又因为$m‘|m$，所以$a^{r-r0}\equiv a^{r-r0+s}(\%m)$，所以$r-r0$也满足条件，这与$r$的最小性矛盾，所以$r0=r$，$m=a^rm‘$

另一方面，在$(3)$式中，易知$(a,a^s-1)=1$,所以$(a^r,a^s-1)=1$

故$m‘|a^{s}-1$，$a^s\equiv 1(\%m‘)$

因为$(a,m’)=1$，根据欧拉定理得$a^{\varphi (m‘)}\equiv 1(\% m‘)$
所以$s|\varphi (m‘)$

又因为$m=a^{r}m‘$，$(a,m‘)=1$，所以$\varphi(m‘)|\varphi(m)$

所以$s|\varphi (m)$

所以结论$(2)$可描述为：

$$a^0,a^1,a^2,...,a^{r-1},a^r,a^{r+1},...,a^{r+\varphi (m)-1},a^r,a^{r+1},...(\%m)$$

从$a^0$到$a^{r-1}$不是重复的，但是从$a^r$开始，会循环出现$a^r,a^{r+1},...,a^{r+\varphi (m)-1}$，循环节长度为$\varphi (m)$$......(5)$

因为$m=a^rm‘$，所以$\varphi(m)\geq \varphi(a^r)\geq a^{r-1}(a-1)\geq r$

所以结论$(5)$又可以描述为：从$a^0$到$a^{\varphi(m)-1}$不是重复的，但是从$a^{\varphi(m)}$开始，会循环出现$a^\varphi(m),a^{\varphi(m)+1},...,a^{\varphi(m)+\varphi (m)-1}$，循环节长度为$\varphi (m)$$......(5)$

所以$$a^b\equiv a^{b\%\varphi(m)+\varphi(m)}(\%m),其中b\geq \varphi(m)$$

另外，如果$b < \varphi(m) $直接快速幂就可以了。

来看一道例题

题目描述

C同学竟然卡题了！而且还卡在一个不难的题目上。题目是这样的：

定义a^b为a的b次方，并且^是满足右结合的，即a^b^c^d=a^(b^(c^d))。例如，2^3^2=2^(3^2)=2^9=512。

现在给定n个数a1，a2，…，an，求a1 ^ a2 ^ … ^ an对p取模的值。

输入格式

输入包括多组数据。

第一行一个整数T，表示数据组数。

接下来每组数据第一行两个整数n,p，第二行n个整数依次描述a1到an。n，p，ai的意义与题目描述一致。

输出格式

对于每组数据输出一行，包含一个整数，即a1 ^ a2 ^ … ^ an对p取模的值。

输入样例

5 13

2 2 2 2 2

3 9

2 3 2

输出样例

数据范围

对于20%的数据，保证n=2；

对于另外30%的数据，保证n≤4，并且a1 ^ a2 ^ … ^ an的位数≤1000，数据组数<=5；

对于100%的数据，保证2≤n≤20，0<p,ai<10^7，数据组数≤100。

我们在求快速幂的时候看一下有没有大于等于mod即可

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<utility>
#include<set>
#include<bitset>
#include<vector>
#include<functional>
#include<deque>
#include<cctype>
#include<climits>
#include<complex>
//#include<bits/stdc++.h>适用于CF,UOJ，但不适用于pojusingnamespace std;

typedef longlong LL;
typedef double DB;
typedef pair<int,int> PII;
typedef complex<DB> CP;

#define mmst(a,v) memset(a,v,sizeof(a))
#define mmcy(a,b) memcpy(a,b,sizeof(a))
#define fill(a,l,r,v) fill(a+l,a+r+1,v)
#define re(i,a,b)  for(i=(a);i<=(b);i++)
#define red(i,a,b) for(i=(a);i>=(b);i--)
#define ire(i,x) for(typedef(x.begin()) i=x.begin();i!=x.end();i++)
#define fi first
#define se second
#define m_p(a,b) make_pair(a,b)
#define p_b(a) push_back(a)
#define SF scanf
#define PF printf
#define two(k) (1<<(k))
#define SIZE(x) (int(x.size())

template<class T>inline T sqr(T x){return x*x;}
template<class T>inline void upmin(T &t,T tmp){if(t>tmp)t=tmp;}
template<class T>inline void upmax(T &t,T tmp){if(t<tmp)t=tmp;}

inline int sgn(DB x){if(abs(x)<1e-9)return0;return(x>0)?1:-1;}
const DB Pi=acos(-1.0);

int gint()
  {
        int res=0;bool neg=0;char z;
        for(z=getchar();z!=EOF && z!=‘-‘ && !isdigit(z);z=getchar());
        if(z==EOF)return0;
        if(z==‘-‘){neg=1;z=getchar();}
        for(;z!=EOF && isdigit(z);res=res*10+z-‘0‘,z=getchar());
        return (neg)?-res:res; 
    }
LL gll()
  {
      LL res=0;bool neg=0;char z;
        for(z=getchar();z!=EOF && z!=‘-‘ && !isdigit(z);z=getchar());
        if(z==EOF)return0;
        if(z==‘-‘){neg=1;z=getchar();}
        for(;z!=EOF && isdigit(z);res=res*10+z-‘0‘,z=getchar());
        return (neg)?-res:res; 
    }

constint maxn=25;

int n,p,s;
int a[maxn],b[maxn],c[maxn],d[maxn];

int mul(int x)
  {
      int i,res=x;
      for(i=2;i*i<=x;i++)
        if(x%i==0)
          {
              while(x%i==0)x/=i;
              res=res/i*(i-1);
          }
      if(x>1)res=res/x*(x-1);
      return res;
  }

int getpow(int a,int k,int modd)
  {
      LL res=1,x=a,flag=0;
      for(;k;k>>=1)
          {
              if(k&1)
                  {
                      if(res*x>=modd) flag=1;
                      res=res*x%modd;
                    }
                if(k==1)break;
                if(x*x>=modd)flag=1;
                x=x*x%modd;
            }
        if(flag)res+=modd;
      return res;
  }

int main()
  {
      freopen("pow.in","r",stdin);
      freopen("pow.out","w",stdout);
      int i,j,T=gint();
      while(T--)
        {
            n=gint();p=gint();mmst(a,0);mmst(b,0);mmst(c,0);mmst(d,0);
            re(i,1,n)a[i]=gint();
            s=0;for(int t=p;t!=1;t=mul(t))b[++s]=t;
            re(j,1,s)
                  {
                      c[j]=a[n]%b[j];
                      if(a[n]>=b[j])c[j]+=b[j];
                    }
            red(i,n-1,1)
              {
                  re(j,1,s)d[j]=getpow(a[i],c[j+1],b[j]);
                  re(j,1,s)c[j]=d[j];
              }
            PF("%d\n",c[1]%p);
        }
      return0;
  }

View Code

原文：http://www.cnblogs.com/maijing/p/5046628.html

内容总结

以上是互联网集市为您收集整理的指数循环节全部内容，希望文章能够帮你解决指数循环节所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1249740.html

来源：【匿名】

【上一篇】绘制特殊图形【下一篇】关于IE的RegExp.exec的问题

更多 ►

【指数循环节】教程文章相关的互联网学习教程文章

$$求证a^b\equiv a^{b\%\varphi(m)+\varphi(m)}(\%m),其中b\geq \varphi(m)$$我们模$m$最多只有$m$种结果，所以根据鸽巢原理，在$$a^0,a^1,...,a^m(\%m)$$这$m+1$个数中，一定存在最小的$r$和最小的$s$，满足$a^r\equiv a^{r+s}(\%m)$且$r+s\leq m.$$......(1)$所以序列其实是这样的：$$a^0,a^1,a^2,...,a^{r-1},a^r,a^{r+1},...,a^{r+s-1},a^r,a^{r+1},...(\%m)$$也就是说，从$a^0$到$a^{r-1}$不是重复的，但是从$a^r$开始，会循环...

plsql程序中循环语句的使用【图】

原文：http://www.cnblogs.com/hwgok/p/7373592.html

循环队列FIFO原理及C实现【代码】【图】

循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针。定义一个循环队列结构：#define FIFO_HEAD(name, type) struct name { struct type *fifo; ...

while循环

语法：while(循环条件){//循环操作}就是在什么条件成立时不断地做什么事情。例子：循环输出一百次好好学习；int i=1;while(i<=100){System.out.println("第"+i+“次输出：好好学习”);i++;}上面这个i++，就是1到100循环中i变化的规律，每次加1；例子2:public class ShiYan { 　　public static void main(String[] args){ 　　　　Scanner input=new Scanner(System.in); 　　　　　　String am; 　　　　　　System.out.prin...

循环结构实验报告【代码】【图】

C程序设计实验报告实验项目： 5.3.1习2 5.3.2习2 5.3.3 5.3.4 5.3.5习1 5.3.5习2 5.3.5习3 姓名：李宏远实验地点：1教524 实验时间：2021.5.6 一、实验目的与要求 (1)熟练掌握使用while. d-.while 及for语句实现循环的方法。 (2)了解3种循环语句的区别和转换、各自的适应性、循环嵌套的使用。 (3)掌握在循环语句中使用break和continue语句改变程序流程的方法。 (4)能在程序设计中用循环的方法实现各种算法。二、实验内容...

VB的判断语句和循环语句

判断语句?If语句if语句共有4种写法: 第一种语法: If 条件判断语句 then 程序代码第二种语法:If 条件判断语句 then 程序代码 else 程式代码第三种语法: If 条件判断语句 then 程式代码 Else 程式代码 End if 第四种语法 If 条件判断语句 then ...

day10-选择结构、循环结构（while循环、do...while循环）【图】

选择结构 if单选择结构我们很多时候需要去判断一个东西是否可行，然后我们才去执行，这样一个过程在程序中用if语句来表示。语法 if (布尔表达式){ //如果布尔表达式为true将执行的语句 }if双选择结构那现在有个需求，公司要收购一个软件，成功了，给人支付100万元；失败了，自己找人开发。这样的需求用一个if就搞不定了，我们需要有两个判断，需要一个双选择结构，所以就有了if-else结构。语法 if(布尔表达式){ ...

循环题目【代码】

1.下面代码的执行结果为（） #include <stdio.h> int main() {int i = 0;for (i = 0; i < 10; i++) {if (i = 5)printf("%d,", i);}return 0; } A.1,2,3,4,5,6,7,8,9,10B.5,5,5,5,5,5,5,5,5,5C.死循环的打印5D.0,1,2,3,4,5,6,7,8,9正确答案选：C 解析：if(i=5）是赋值！！！2.关于if语句说法正确的是（）A.if语句后面只能跟一跳语句。B.if语句是一种分支语句，可以实现单分支，也可以实现多分支。C.if语句中0表示假，1表示真。D.els...

for、foreach和MoveNext循环效率粗比较【代码】

今天没事对for循环、foreach循环、MoveNext循环，执行效率进行了对比；粗略测试代码如下： staticvoid Main(string[] args){#region 三种方式循环执行效率测试List<int> intList = new List<int>();for (int i = 0; i < 100000000; i++){intList.Add(i);}#region for循环执行时间测试Stopwatch sw_1 = new Stopwatch();string excuteTime_1;int sum1 = 0;sw_1.Start();for (int i = 0; i < intList.Count; i++){sum1 += intList[i]...

(转)SQL中的循环、for循环、游标【代码】【图】

DECLARE My_Cursor CURSOR --定义游标FOR (SELECT * FROM dbo.MemberAccount) --查出需要的集合放到游标中OPEN My_Cursor; --打开游标FETCH NEXT FROM My_Cursor ; --读取第一行数据WHILE @@FETCH_STATUS = 0 BEGIN --UPDATE dbo.MemberAccount SET UserName = UserName + ‘A‘ WHERE CURRENT OF My_Cursor; --更新 --DELETE FROM dbo.MemberAccount WHERE CURRENT OF My_Cursor; --删除 FETCH NEXT FROM...

Spring源码--debug分析循环依赖--构造器注入【代码】【图】

目的：源码调试构造器注入，看看是怎么报错的。 spring：5.2.3 jdk：1.8 一、准备首先准备两个循环依赖的类：userService和roleServic<bean id="userService" class="com.chris.spring.service.UserServiceImpl"><constructor-arg ref="roleService"/> </bean> <bean id="roleService" class="com.chris.spring.service.RoleService"><constructor-arg ref="userService"/> </bean>二、开始调试因为依赖注入的触发点是容器初始化所...

Node.js回调函数和事件循环机制

1.Node.js回调函数 Node.js 是单进程单线程应用程序，但是因为 V8 引擎提供的异步执行回调接口，通过这些接口可以处理大量的并发，所以性能非常高。所以，node.js是采用异步编程，具体实现就是回调函数。回调函数在完成任务后就会被调用，Node 使用了大量的回调函数，Node 所有 API 都支持回调函数。因此，同步是按顺序执行的，是阻塞的，而异步是非阻塞的，是不需要按顺序的，所以如果需要处理回调函数的参数，我们就需要写在回调...

smarty模板引擎中section循环loop与total的区别【代码】

在smarty模板引擎的section循环中$data=[101,102,103,105,104];section的两个属性total与loop{section foo $data start=1 step=2}　　{$smarty.section.foo.total}--输出2　　{$smarty.section.foo.loop}--输出5 {/section}意即：使用total输出的是循环执行的次数，使用loop输出的是所循环数据的count原文：http://www.cnblogs.com/Bin-x/p/4563627.html

with_items标准循环【代码】

1.为不同用户定义不同组--- - hosts: web2remote_user: roottasks:- user:name: "{{item.name}}"group: "{{item.group}}"password: "{{‘123456‘|password_hash(‘sha512‘)}}"with_items:- {name: "aa", group: "users"}- {name: "bb", group: "mail" }- {name: "cc", group: "wheel"}- {name: "dd", group: "root" }运行# ansible-playbook add.yml 注意item.name 中间是点，组是自己存在的 2.嵌套循环，循环添加多用户--- - ...

斐波那契数组-递归和循环实现

static void Main(string[] args) { Console.WriteLine(getnumfor(100)); Console.ReadKey(); } static long getnum(long index) { if (index==1||index==2) { return 1; } else { return getnum(index - 1) + getnum(index - 2); } } static long getnumfor(...