Show all threads Hide all threads Show all messages Hide all messages | WA on test 1, am I misunderstanding the output format? | sweepea | 1110. Power | 20 Feb 2024 17:27 | 1 | del Edited by author 20.02.2024 17:47 | WA10, can you give me tests? | Daniil | 1110. Power | 2 Aug 2021 03:01 | 5 | 1 4 3 the answer is 3, not -1 | Help I got WA test 6 | Juan H | 1110. Power | 22 Oct 2020 11:59 | 2 | 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 | IDEA | mosiur | 1110. Power | 22 Oct 2020 11:57 | 1 | IDEA mosiur 22 Oct 2020 11:57 | Please, anybody know What is the TEST #6 ? | dake | 1110. Power | 22 Jun 2020 09:08 | 2 | Edited by author 26.10.2013 22:11 | Because of p*=(i%m) was WA | Lieutenant | 1110. Power | 28 Oct 2019 11:48 | 2 | 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 | help | Vorobeva | 1110. Power | 17 Sep 2019 02:10 | 1 | help Vorobeva 17 Sep 2019 02:10 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 | Accepted | Alexei | 1110. Power | 5 Aug 2019 22:46 | 1 | 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; } | Limit is too small | Scythe (Berinde Radu) | 1110. Power | 28 Mar 2019 19:39 | 4 | 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? | what is wrong with my code ??? | Adkham | 1110. Power | 8 Feb 2018 02:23 | 1 | #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 | Java or C++ problem !?!?!? | Valiok | 1110. Power | 9 Nov 2017 19:46 | 2 | 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 ??? | what is the difference between this code and that code, still get wrong | VNeo | 1110. Power | 16 Jul 2017 18:32 | 11 | 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 | netman | 1110. Power | 6 Feb 2017 02:07 | 3 | 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; | I get accept,but i don't why | aurora | 1110. Power | 6 Sep 2016 13:17 | 2 | #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. | Help.Помогите найти ошибку | Vasurov | 1110. Power | 20 Nov 2015 09:32 | 2 | 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. | Please, give me some test!!! | Algorithmus_UA(algorithmus@univ.kiev.ua) | 1110. Power | 27 Oct 2015 21:20 | 7 | 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 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 | Hint | pav1uxa | 1110. Power | 29 Dec 2014 23:20 | 1 | Hint pav1uxa 29 Dec 2014 23:20 del Edited by author 06.01.2015 21:37 | Done...!!! | Bahodir _ TUIT | 1110. Power | 25 Nov 2014 19:29 | 1 | done... Edited by author 30.11.2014 01:32 Edited by author 30.11.2014 01:32 | Pascal - AC, but Java - WA | Maxim_tmn | 1110. Power | 10 Apr 2014 17:17 | 1 | 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(); } } | Tests and hints here. | 2BEB8CEC | 1110. Power | 10 Apr 2014 17:06 | 2 | 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 |
|
|