(thought I'd be able to edit my post with an example before you read it)
![:wink:](./images/smilies/icon_wink.gif)
Moderator: Board moderators
#include <stdio.h>
int min;
gcd(int a, int b){
if(b>a) gcd(b,a);
if(b==0) {
min=a;
return 1;
}
gcd(b,a%b);
}
calc(int n,int neg){
int i=3,j=0;
min=1;
if(n%2==0){
while(n%2==0){
n/=2;
j++;
}
min=j;
if(j==1){
printf("1\n");
return 1;
}
}
j=0;
while(i*i<=n){
if(n%i==0){
while(n%i==0){
n/=i;
j++;
}
if(j==1){
printf("1\n");
return 1;
}
if(min==1) min=j;
else gcd(min,j);
if(min==1){
printf("1\n");
return 1;
}
}
j=0;
i+=2;
}
if(neg==1){
if(min%2==0)
while(min%2==0) min/=2;
printf("%d\n",min);
}
else
printf("%d\n",min);
}
int main()
{
int n;
while(scanf("%d",&n)&n!=0){
if(n==-2147483647 || n==2147483647) printf("1\n");
if(n<0) calc(-n,1);
else calc(n,0);
}
return 0;
}
Code: Select all
-1
-16
-27
-81
-243
-244140625
-48828125
-134217728
1
17
25
125
81
107374182
134217728
2147483647
1073741824
-2147483648
0
Code: Select all
1
1
3
1
5
3
11
27
1
1
2
3
4
1
27
1
30
31
Code: Select all
#include<iostream.h>
#include<math.h>
const int maxprime=70000;
bool isprime[maxprime];
int prime[maxprime],primesize;
int gcd2n(int a,int b){
int c;
if(a<b){
c=a;
a=b;
b=c;
}
c=a%b;
while(c>0){
a=b;
b=c;
c=a%b;
}
return b;
}
int gcd(int A[],int n){
int I,ans;
if(n==1)return A[0];
ans=gcd2n(A[n-2],A[n-1]);
for(I=0;I<n-2;I++)
ans=gcd2n(A[I],ans);
return ans;
}
void main(){
int ans,I,J,n,s,m,factno,factpow[40],flag;
for(I=0;I<maxprime;I++)
isprime[I]=true;
isprime[0]=isprime[1]=false;
for(I=2;I<maxprime;I++)
if(isprime[I]){
prime[primesize++]=I;
for(J=I+I;J<maxprime;J+=I)
isprime[J]=false;
}
cin>>n;
while(n!=0){
if(n==-2147483648){
cout<<31<<endl;
cin>>n;
continue;
}
if(n<0){
n=n*-1;
flag=-1;
}else flag=1;
s=sqrt(n);
m=n;
factno=0;
if(n<maxprime&&isprime[n]){
factpow[0]=1;
factno=1;
}else{
for(I=0;I<primesize&&prime[I]<=s&&m>1;I++)
if(m%prime[I]==0){
factpow[factno]=0;
while(m%prime[I]==0){
m/=prime[I];
factpow[factno]++;
}
if(flag==-1&&(factpow[factno]%2==0))factpow[factno]/=2;
factno++;
if(m<maxprime&&isprime[m]){
factpow[factno]=1;
factno++;
m=1;
}
}
if(m>1)
factpow[factno++]=1;
}
ans=gcd(factpow,factno);
cout<<ans<<endl;
cin>>n;
}
}
I think the problem in your algorithm is inI'm getting WA and don't undrestand where is my mistake.could someone please help me?
my algorithm:
1)producing prime numbers up to the sqrt of MAX_int(our limit)
2)when reading an input produce all powers of its primefactors and store them
3)getting gcd between powers
4)(if n<0 and gcd%2==0 )gcd/=2
5)for case n=-2147483648 I just print 31 and go to read next input
Code: Select all
static int[] findPrimes(int n) {
int primes[] = new int[100000];
int numPrime = 0;
int MAX = n+1;
boolean notPrime[] = new boolean[MAX];
for(int i=2; i<MAX; i+=2) {
if(notPrime[i]) continue;
primes[numPrime++] = i;
for(int j=i; j<MAX; j+=i) {
notPrime[j] = true;
}
if(i==2)
i--;
}
int results[] = new int[numPrime];
System.arraycopy(primes, 0, results, 0, numPrime);
return results;
}
public static void main(String args[]) throws Exception {
int primes[] = findPrimes((int)Math.sqrt(Integer.MAX_VALUE));
while(true) {
String line = readLine();
if(line.equals("")) continue;
int N = toInt(line);
if(N == 0) break;
if(N == Integer.MIN_VALUE) {
println(31);
continue;
}
int origN = N;
N = (N < 0 ? -N : N);
HashMap<Integer, Integer> powers = new HashMap<Integer, Integer>();
for(int p : primes) {
if(N == 1)
break;
if(N%p != 0)
continue;
powers.put(p, 0);
while(N%p == 0) {
powers.put(p, 1 + powers.get(p));
N/=p;
}
}
if(N > 1)
powers.put(N, 1);
int power = -1;
for(int p : powers.values()) {
if(power == -1)
power = p;
if(power != p) {
power = -1;
break;
}
}
if(power == -1 || power == 1) {
println(1);
continue;
}
if(origN < 0) {
while(power%2 == 0) {
power/=2;
}
}
println(power);
}
flush();
}
Code: Select all
2025
-2025
4624
4900
512
176400
1540798875
-1540798875
648000
746496
2985984
-2985984
-612220032
204073344
3779136
-75325538
75325538
418161601
-418161601
-2147483648
0
Code: Select all
2
1
2
2
9
2
3
3
1
2
6
3
7
1
2
1
1
4
1
31