jzoj3520 原根

2019-04-14 19:36发布生成海报

站内文章 / 模拟电子

9652 0

3520. 【NOIP2013模拟11.7B组】原根(math)

Description

Input

有且只有一个正整数m。

Output

以递增序依次输出模m的所有原根，每行输出一个原根。

如果不存在模m的原根，输出-1。
分析：暴力找原根即可。
代码

var
  i,j,n,s:longint;
  fl:boolean;
  k:int64;

function gcd(a,b:longint):longint;
var
  r:longint;
begin
  r:=a mod b;
  while r>0 do
    begin
      a:=b;
      b:=r;
      r:=a mod b;
    end;
  exit(b);
end;

begin
  assign(input,'math.in');reset(input);
  assign(output,'math.out');rewrite(output);
  readln(n);
  for i:=1 to n do
    if gcd(n,i)=1 then inc(s);
  if n=1 then
    begin
      writeln(1);
      halt;
    end;
  for i:=1 to n-1 do
    if gcd(n,i)=1 then
      begin
        k:=i;
        for j:=1 to s do
          begin
            if (k=1) then
              begin
                if j=s then
                  begin
                    writeln(i);
                    fl:=true;
                  end;
                break;
              end;
            k:=(k*i) mod n;
          end;
      end;
  if not fl then writeln(-1);
  close(input);close(output);
end.

jzoj3520 原根

Ta的文章更多 >>

热门文章

jzoj3520 原根

Ta的文章 更多 >>

热门文章

举报内容

检举类型

检举原因

检举说明(必填)

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮

Ta的文章更多 >>