Description
Statements
Mathematician Michael is dreaming how he becomes a Minister of Education in Russia and tries his innovative experimental educational program in Maths in an elementary school. The main feature of this program is learning arithmetical operations in fields of integers modulo prime numbers instead of fields of real numbers. Impressed by his idea, Michael has started to write a Maths textbook for the 1st grade kids and is already preparing exercises to find a square root in modular arithmetic.
In each such exercise an integer x is given, and it's needed to find its square root modulo prime number p, which is also given. The correct answer for such task is an integer s, such that s·s and x have the same remainder after division by p. In other words, the number has to leave no remainder after division by p. It must be said that the square root s doesn't exist for some numbers x.
To speedup the process of preparing tasks in this topic, Michael decided to write a program that finds square roots modulo given prime number p for all numbers x from 0 to , or tells that the corresponding square root doesn't exist.
Input
The first line contains a prime number p (2 ≤ p ≤ 106). A prime number has exactly two different divisors.
Output
Output p space-separated integers, the i-th of which must be equal to the square root of modulo p. All numbers must be between 0 and
. If some square root doesn't exist, output - 1 instead of it, and if there are multiple square roots for some i, output any of them.
Sample Input
5
0 4 -1 -1 3
7
0 1 3 -1 5 -1 -1
Hint
In the first sample: ,
.
打表可知其由1到n+1则打表直接可得出结果
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
const int inf_int = 2e9;
const long long inf_ll = 2e18;
#define inf_add 0x3f3f3f3f
#define mod 1000000007
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;
while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')
fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,
rx=getchar();return ra*fh;}
//#pragma comment(linker, "/STACK:102400000,102400000")
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
ll a[2000005];
int main()
{
ll n,i,j;
cin >> n;
printf("0\n");
for(ll i=1;i<=n/2;i++)
{
a[i*i%n] = i;
}
for(ll i=1;i<n;i++)
{
if(a[i])
printf("%lld\n",a[i]);
else
printf("-1\n");
}
return 0;
}