九九归一

稍作尝试可得三类情况, 分类讨论:
1. 根本就没有循环/循环节大于phi(n), 当且仅当a, n不互质
2. 循环节等于phi(n)
3. 循环节为phi(n)的因数

2, 3类情况需要通过运算来判别.
通过快速幂来加速运算(又是二进制拆分思想…)
代码不是我的.

#include
#includeusing namespace std;
const int N=100100;
int p[N],c[N],ans,n,m,k,x,tot,flag;long long pow(long long x,int len)
{if (len==1) return x;long long t=pow(x,len/2);if (len%2)return t*t%k*(long long)x%k; elsereturn t*t%k;
}int main()
{scanf("%d%d",&n,&m);k=n;ans=n;for (int i=2;i*i<=n;i++)if (n%i==0){while (n%i==0) n/=i;ans=ans/i*(i-1);}if (n!=1) ans=ans/n*(n-1);for (int i=2;i*i<=ans;i++)if (ans%i==0){p[++tot]=i;if (ans/i!=i)p[++tot]=ans/i;}while (m--){scanf("%d",&x);flag=1;for (int i=1;i<=tot;i++)if (pow(x,p[i])==1){flag=0;break;}if (flag && pow(x,ans)==1)printf("1"); elseprintf("0");}printf("\n");
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！