del Edited by author 20.02.2024 17:47 ? 1 4 3 the answer is 3, not -1 I got wrong answer beacuse of test 6 Someone please explain what is test 6 Program in C #include <stdio.h> #include <math.h> int main() { long int n,m,y; int x,cont=0,aux1; scanf("%d %d %d",&n,&m,&y); for (int i = 0; i <=m-1 ; ++i) { aux1=pow(i,n); if (aux1%m == y) { printf("%d ",i); cont++; } } if (cont == 0) { printf("-1\n"); } return 0; } Edited by author 13.10.2020 05:27 Edited by author 26.10.2013 22:11 Because of p*=(i%m) was WA. When I wrote p=(p*i)%m instead of p*=(i%m) then I got AC Why??? p*=(i%m) <==> p=p*(i%m) != (p*i)%m class Program { public static void Mod(int N, int M, int Y) { int f = 0, t = -1; for (int i = 0; i < M; i++) { int X = i; long y = X; for (int j = 2; j < N + 1; j++) { y = y * X; y = y % M; } if (y == Y) { if (f > 0) Console.Write($" "); Console.Write($"{X}"); f++; } } if (f == 0) Console.Write($"{t}"); Console.WriteLine(); } } Edited by author 17.09.2019 02:10 This is my solution O(M log N) #include <bits/stdc++.h> #define in(x) freopen(x,"r",stdin) #define out(x) freopen(x,"w",stdout) #define N 100500 #define oo ll(1e16) #define P pair < int, int > #define PP pair < pair < int, int >, int > #define F first #define S second #define pb push_back #define el endl #define base ll(1e9 + 7) using namespace std; typedef long long ll; typedef long double ld; int n, m, y; bool o; int bin(int x, int st) { int res = 1; for(; st > 0;) { if (st & 1) res = (res * x) % m; x = (x * x) % m; st >>= 1; } return res; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m >> y; o = 0; for (int i = 1; i < m; i++) { int cur = bin(i, n); if (cur == y) cout << i << ' ', o = 1; } if (!o) cout << -1; } The problem limits are too small. You can get ac with the O(N^2) algorithm which is VERY straightforward. The limit should force you to use the O (log N) algorithm to compute X^N (%M) > The problem limits are too small. > You can get ac with the O(N^2) algorithm which is VERY > straightforward. The limit should force you to use the O > (log N) algorithm to compute X^N (%M) O(log N) !? Isn't it O(MlogN) ? well,if it's really O(log N) , please tell me how :) I got AC with 0.031 373 KB using brute force. This is the dummest task I made. Tell them to read the O(M log N) algorith in Introduction in algo(Coreman) This sadly is my AC source: var i,j,k,l,m,n:longint; ok:boolean; begin readln(n,m,k); for i:=0 to m-1 do begin l:=i; for j:=1 to n-1 do l:=(l*i) mod m; if l mod m=k then begin write(i,' '); ok:=true; end; end; if not ok then write(-1); end. Edited by author 10.05.2004 17:49 Hello, explain to me why you use l:=(l*i) mod m;(...mod m)?!! Why? #include<iostream> #include<cmath> using namespace std; int func(int k, int n, int m) { if(n == 0) return 1; else return func(k, n-1, m)*k%m; } int main() { int n, m, y, x, i = 0; int b; bool flag = true; cin >> n >> m >> y; if((n >0 && n < 999) && (m > 1 && m < 999) && (0 < y && < 999)) { while(i < m) { x = func(n, i, m); if(x == y) { cout << i << ' '; flag = false; } i++; } if(flag) cout << "-1"; } else cout << "-1"; return 0; } Edited by author 08.02.2018 02:25 Edited by author 08.02.2018 02:27 Here is my java code : import java.util.Scanner; public class Example{ public static void main(String []args){ Scanner in = new Scanner(System.in); int number1,number2,number3; int [] array; int position=0; boolean check=false; int sth; number1=in.nextInt(); number2=in.nextInt(); number3=in.nextInt(); array = new int[number2]; for(int i=0;i<=number2-1;i++){ sth=(int)Math.pow(i,number1); if((sth-number3)%number2==0){ array[position]=i; position++; check=true; }else if(i==number2-1 && check==false){ System.out.println(-1); System.exit(0); }
} for(int p=0;p<position-1;p++){ for(int j=p+1;j<position;j++){ if(array[p]>array[j]){ int t=array[p]; array[p]=array[j]; array[j]=t; } } } for(int i=0;i<position;i++){ System.out.print(array[i] + " "); } System.out.println(); } } I get an error on test#3 . And on my C++ solution i get an error on test#6. #include<iostream> #include<cmath> using namespace std; int main(void){ unsigned short int N,M,Y; cin>>N>>M>>Y; unsigned short int X[M]; unsigned short int position=0; bool some_check=false; int sth; for(int i=0;i<=M-1;i++){ sth=pow(i,N); if((sth-Y)%M==0){ X[position]=i; position++; some_check=true; } else if(i==M-1 && some_check==false){ cout<<-1<<endl; return 0; } } for(unsigned short int i=0;i<position-1;i++){ for(unsigned short int j=i+1;j<position;j++){ if(X[i]>X[j]){ swap(X[i],X[j]); } } } for(unsigned short int i=0;i<position;i++){ cout<<X[i]<<" "; } cout<<endl; return 0; } Please,any ideas ??? i got WA#6 when i use this code #include <iostream> #include <cmath> using namespace std; long int n,m,y,p,q,r[999]; int main(){ cin>>n>>m>>y; for (int i=0;i<m;i++){ if (lround(pow(i,n)) % m==y){ q++; r[q]=i; } } if (q==0){ cout<<"-1"; } else { for (int i=1;i<=q;i++){ cout<<r[i]<<' '; } } } but when i use neighbored code which is already acc, and tested some test case between them, it give me same results. whats probably wrong in my code by the way, the neighbored code is pascal language, but the point is, i just used that for test case. oh , i forgot. The neighbored code is this var ans: array[1..1000] of longint; n,m,y,q,i: longint; function BinPow(x,y: longint): longint; begin if y=1 then BinPow:=x else if y mod 2=0 then BinPow:=sqr(BinPow(x,y div 2)) mod M else BinPow:=(sqr(BinPow(x,y div 2))*x) mod M; end; begin readln(n,m,y); q:=0; for i:=0 to m-1 do begin if BinPow(i,n)=y then begin inc(q); ans[q]:=i; end; end; for i:=1 to q do write(ans[i],' '); if q=0 then writeln(-1); end. netman from timus judge, sorry for copied your code. Look at the limitations. You can have X^N=998^998. That is 9,98e1000. Look at fundamental data types range. double is something like not greater (-1e309;1e309) with 15 digits after point . That is much smaller than you need. So, in function pow there is an overflow. That means double LOSES PRECISION. And if actually X^N mod M == Y for some big X^N them your program can't see it. Because last digits of X^N are lost due to an overflow. And in netman's code, there is such a function, that keeps ONLY the last digits. So, the main difference is. Your code keeps MOST significant digits. netman's code keeps LEAST significant digits. More precisely, netman's code keeps last approximately log10(M) +1 digits. That is, if the number is say 12345...{lot of digits}... 6789 Then your code keeps 1234 as digits and keeps additional information only about HOW MANY digits are before 1234. And netman's code keeps only digits 6789. so, what i've gonna do?. I still cant find the solution. is there are any function like pow, but can keep LEAST significants digits like you said before? still get WA#6, after change lround into llround. but why?, llround is the function that round nearest decimal into long long integer. it much more greater than lround. What is maximal long long? something like 1e20. It is so SMALL against 998^998. int pow(int X, int N, int M) { if(N<1) return 1; int res=pow(X, N>>1, M); res=(res*res)%M; if(N&1) return (X*res)%M; return res; } I got AC right now with this power function. This is the right solution Sorry for my english var ans: array[1..1000] of longint; n,m,y,q,i: longint; function BinPow(x,y: longint): longint; begin if y=1 then BinPow:=x else if y mod 2=0 then BinPow:=sqr(BinPow(x,y div 2)) mod M else BinPow:=(sqr(BinPow(x,y div 2))*x) mod M; end; begin readln(n,m,y); q:=0; for i:=0 to m-1 do begin if BinPow(i,n)=y then begin inc(q); ans[q]:=i; end; end; for i:=1 to q do write(ans[i],' '); if q=0 then writeln(-1); end. My solve in C++: #include <iostream> #include <string> #include <vector> #include <set> #include <queue> #include <map> #include <stack> #include <algorithm> #include <bitset> #include <cstring> #include <cmath> #include <cstdlib> #include <cstdio> #include <iomanip> #define F first #define S second #define ll long long #define len length() #define sqr(x) x*x #define pb push_back #define mp make_pair #define sz(x) ((int) (x).size()) #define all(x) x.begin(), x.end() #define allr(x) x.rbegin(), x.rend() #define bp(x) __builtin_popcount(x) #define INF numeric_limits<long long int>::max() #define frp freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++) const int maxn = (int)1e6; const int mod = (int)1e9 + 7; using namespace std; __int64 n,m,y;
int binpow(int a, int n){ if (n == 0) return 1; if (n % 2 == 1) return (binpow (a, n-1)*a)%m; else{ int b = (binpow(a, n/2)); return (b*b)%m; } }
bool ok; main(){ scanf("%I64d%I64d%I64d",&n,&m,&y); for(int i=0; i < m; i++){ if(binpow(i,n)%m==y){ cout<<i<<" "; ok=1; } } if(!ok) return cout<<"-1",0;
return 0; } What it is? else if y mod 2=0 then BinPow:=sqr(BinPow(x,y div 2)) mod M else BinPow:=(sqr(BinPow(x,y div 2))*x) mod M; #include<iostream> using namespace std; int main() { int N, M, Y; while (cin >> N >> M >> Y) { int f = 0,t=-1; for (int i = 0; i < M; i++) { int x = i; long long y = x; for (int j = 2; j < N + 1; j++) { y *= x; y %= M; } if (y== Y) { if (f > 0) cout << ' '; cout << x ; f ++; } } if (f == 0) cout << t; cout << endl; } return 0; } why it can get accept,but this one get WA #include<iostream> using namespace std; int main() { int N, M, Y; while (cin >> N >> M >> Y) { int f = 0,t=-1; for (int i = 0; i < M; i++) { int x = i; long long y = x; for (int j = 2; j < N + 1; j++) { y *= x; } if (y%M== Y) { if (f > 0) cout << ' '; cout << x ; f ++; } } if (f == 0) cout << t; cout << endl; } return 0; } Your second program assumes that all x^N are less than long long limit. It isn't true. 10^999 requires about 999 digits. long long limit is about 19 digits. var m, n, b, y, k, x: integer; function St(x, n: integer): integer; var i, f: integer; begin f := 1; for i := 1 to n do f := f * x; St := f; end; begin readln(n, m, y); for x := 0 to m - 1 do begin b := st(x,n); if (b mod m) = y then begin write(x,' '); k := k + 1; end; end; if k = 0 then writeln(-1); end. I take WR!!! I don't know what s wrong!!! ---------------------------------MY PROGRAM------------------------- var N,M,Y:longint; a:array[1..15]of byte; b:array[1..15]of longint; d:array[1..1000]of integer; h,x,l:integer; i,j,s:longint; begin assign(input,'1110.dat'); reset(input); readln(N,M,Y); x:=N; for i:=1 to 15 do begin a[i]:=x mod 2; x:=x div 2; if x = 0 then break; end; l:=i; for i:=0 to M-1 do begin b[1]:=i; for j:=2 to l do begin b[j]:=(b[j-1]*b[j-1]) mod M; end; s:=1; for j:=1 to l do if a[j]=1 then begin s:=(s*b[j]) mod M; end; if s = Y then begin inc(h); d[h]:=i; end; end; for i:=1 to h-1 do write(d[i],' '); if h<>0 then writeln(d[h]); end. The answer for test 1 2 3 Should be -1 GL > The answer for test > 1 2 3 > Should be > -1 > > GL 0 0 0 _______ Answer: 0 0 0 0 _______ Answer: 0 No, because X in the interval [0, M − 1] I think answer is -1 Since, (0 < N < 999, 1 < M < 999, 0 < Y < 999) the minimum input is: 1 2 1 with the answer 1 Megakrit, This is best test! Thank you! Edited by author 27.10.2015 21:21 del Edited by author 06.01.2015 21:37 done... Edited by author 30.11.2014 01:32 Edited by author 30.11.2014 01:32 In Pascal I have AC, but in Java - WA, why?? /* package whatever; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ public class Ideone { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out);
int N, M, Y = 0; boolean check = false;
N = in.nextShort(); M = in.nextShort(); Y = in.nextShort();
double p;
if ( ((0<N) && (N<999)) && ((1<M) && (M<999)) && ((0<Y) && (Y<999)) ) { for (int X=0; X<=M-1; ++X) { p = ((Math.pow(X,N)) % M); if (p == Y) { if (X != (M-2)) { out.print(X + " "); } else { out.print(X); } check = true; } } }
if (!check) { out.print("-1"); }
out.flush(); } } A couple of tests that I obtained from my working program: 998 999 972 48 63 159 174 270 285 381 396 492 507 603 618 714 729 825 840 936 951 998 999 900 -1 Scroll down for hint. v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v v Hint: (A*B) MOD C = ((A MOD C) * B) MOD C Edited by author 13.10.2011 19:15 Edited by author 13.10.2011 19:16 With numbers 998 999 972 answer must be -1< because, 1 < M < 999 |
|