【JZOJ A组】原根(math)

2019-04-14 20:33发布

站内文章 / 模拟电子
10354 0 939
class="markdown_views prism-atom-one-light">

Description

在这里插入图片描述

Input

有且只有一个正整数m。

Output

以递增序依次输出模m的所有原根，每行输出一个原根。 如果不存在模m的原根，输出-1。

Sample Input

7

Sample Output

3 5

Data Constraint

50%的数据，m≤ 200。 100%的数据，m ≤ 10000。

Hint

样例解释： 在这里插入图片描述

思路

m很小，直接暴力即可

代码

#include #include #include using namespace std; int m,s; bool b=0; int gcd(int a,int b) { return !b?a:gcd(b,a%b); } int main() { freopen("math.in","r",stdin); freopen("math.out","w",stdout); scanf("%d",&m); if(m==1) { printf("1"); return 0; } for(int i=1; i<=m; i++) { if(gcd(i,m)==1) s++; } for(int i=1; i<=m; i++) { int t=1; for(int j=1; j<=s; j++) { t=t*i%m; if(t==1) { if(j==s) printf("%d ",i),b=1; break; } } } if(!b) printf("-1"); }

热门文章