10139 - Factovisors

[animenologist]

I've tried my code on of nesqi and dumb dan's test input and so far it looks alright, but I still get wrong answer. Any idea what I'm missing? Because I've tried it on every single test case I've come across while searching this board, including cases where there is a prime factor larger than 2^32-1. Any ideas or help would be appreciated.

Code: Select all

Code cut after accepted

EDIT: Got it, thanks.

[rator10]

Could you put some comments on the functions to help us know what the various methods are supposed to be doing? Some of the code is slightly too obfuscated for me to catch what each part does without some understanding of what's going on..

Thanks

[[edit:

btw, nesqi and dumb dan, your test data helped me catch a stupid error in my code where I was trying to get the lowest factorial I'd need to have a given number of primes in a result (like needing 125! to have at least 31 5's in the resulting number), and a special case I completely forgot about, even though it was in the problem specification: 0!

Thanks a bunch for that sample input]]

[animenologist]

Edit: got it, thanks

[ramgopal1987]

Am new here . pls help. I dont know why I am getting Runtime Error for the following code : I checked the test cases of nesqi and dumb dan . Code Working well on those cases.

Code: Select all

import java.io.*;
import java.util.*;
class Main
{
	DataInputStream in;
	int prime[],pow[],len;
	int valval[][];
	int max=(int)Math.pow(1.0*((long)Math.pow(2,31)),0.5)+10;
	public Main() throws IOException
	{
		in=new DataInputStream(System.in);
		//Scanner sc=new Scanner(System.in);
		
		fill();
		for(;;)
		{
			String s=get();
			if(s.equals(""))
				break;
			String ss[]=s.split(" ");
			int n=Integer.valueOf(ss[0]);
			int m=Integer.valueOf(ss[1]);
			
			/*
			if(!sc.hasNext())
				break;
			int n=sc.nextInt();
			int m=sc.nextInt();
			*/int mm=m;
			//handle m=0|1 and n=0|1
			if(m==0)
			{
				put(mm+" does not divide "+n+"!\n");
				continue;
			}
			if(m==1)
			{
				put(mm+" divides "+n+"!\n");
				continue;
			}
			if(n==0||n==1)
			{
				put(mm+" does not divide "+n+"!\n");
				continue;
			}
			boolean flag=true;
			int st=(int)Math.pow(m,0.5);
			for(int i=0;prime[i]<=st;i++)
			{
				
				int cnt;
				for(cnt=0;m%prime[i]==0;m/=prime[i],cnt++);
				pow[i]=cnt;
				int vv=(int)Math.pow(prime[i],pow[i]);
				//boolean ok=cnt(n,prime[i],pow[i]);
				//put(times+"\n");
				if(pow[i]==0)
					continue;
				int req=valval[i][pow[i]-1];
				if(req>n)
				{
					flag=false;
					break;
				}
				if(m==1)
					break;
				//put(prime[i]+" "+pow[i]+" "+m+"\n");
			}
			if(flag)
			{
				if(m==1||m<=n)
				{
					put(mm+" divides "+n+"!\n");
					continue;
				}
					
			}
			put(mm+" does not divide "+n+"!\n");
		}
	}
	void fill()
	{
		prime=new int[max];
		pow=new int[max];
		len=0;
		boolean flag[]=new boolean[max];
		Arrays.fill(flag,true);
		for(int i=2;i<max;i++)
		{
			if(!flag[i])
				continue;
			prime[len++]=i;
			for(int j=i;(long)i*j<max;j++)
				flag[i*j]=false;
			//put(prime[len-1]+"\n");
		}
		//put((long)prime[len-1]*prime[len-1]+"\n");
		//put(len+"\n");
		fill1();
	}
	void fill1()
	{
		valval=new int[len][];
		for(int i=0;i<len;i++)
		{
			int now=(int)(Math.log(Math.pow(2,31)-1)/Math.log(prime[i]));
			valval[i]=new int[now];
			int j=0;
			int kk;
			for(int k=prime[i];j<now;k+=prime[i])
			{
				
				//int pp=(int)(Math.log(k)/Math.log(prime[i]));
				for(int l=k;l%prime[i]==0&&j<now;l/=prime[i])
						valval[i][j++]=k;
				
				
				
			}
			
		}
		/*for(int i=0;i<len;i++)
		{
			put("\nlist for "+prime[i]+"\n");
			for(int j=0;j<valval[i].length;j++)
				put(valval[i][j]+" ");
		}*/
		
	}
	boolean cnt(int n,int val,int need)
	{
		int tot=0;
		for(int i=1;i<=(int)(Math.log(n)/Math.log(val))&&tot<need;i++)
		{
			//put((int)(Math.log(n)/Math.log(val))+" "+i+"\n");
			int tt=(int)(n/Math.pow(val,i));
			tot+=tt;
		}
		if(tot>=need)
			return true;
		return false;
			
	}
	/*Template*/
	public String get() throws IOException
	{
		return in.readLine();
	}
	public void put(String s)
	{
		System.out.print(s);
	}
	public static void main(String args[]) throws IOException
	{
		Main m=new Main();
	}
}

I am precomputing all primes till sqrt(2^31) + one xtra prime in fill() .
In fill1() , valval[][] is filled : valval[j] stores Minimum N whose factorial has j times of prime number prime.

[ramgopal1987]

Got Ac now ... I just added try catch in input getting part ... There seems to be some extra character in end of input ....
I did this and got AC .

Code: Select all

try{
			s=get();
			
				
			if(s.equals(""))
				break;
			String ss[]=s.split(" ");
			n=Integer.valueOf(ss[0]);
			m=Integer.valueOf(ss[1]);
			}
			catch(Exception e)
			{
				break;
			}

[alamgir kabir]

Please help me. I am getting WA. I think it is really a simple problem but i am getting WA.
I use number theory for getting the prime factors of a given factorial then check that the prime factor of the number and the prime factor of the factorial is same or smaller.

Code: Select all

#include<stdio.h>
#include<math.h>

bool facto(long long f, long long num, long long power)
{
    while(f / num > 0 && power > 0)
    {
        power -= (f / num ) ;
        f /= num;
    }
    if(power > 0)
    {
        return false;
    }
    return true;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    long long a, b, i, num, power;
    bool div;
    while(scanf("%lld %lld", &a, &b) == 2)
    {
        num = b;
        div = false;

        if(b == 0)
        {
            printf("0 does not divide %lld!\n", a);
            continue;
        }
        if(a == 0 && b == 1)
        {
            printf("%lld divides %lld!\n", b, a);
            continue;
        }
        for(i = 2; i <= sqrt(num); i ++)
        {
            if(num % i != 0)
            {
                continue;
            }

            div = false;
            power = 0;
            while(num % i == 0)
            {
                num /= i;
                power ++;
            }
            div = facto(a, i, power);
            if(!div)
            {
                break;
            }
        }
        if(div && num > 1)
        {
            div = facto(a,num,1);
        }
        if(div)
        {
            printf("%lld divides %lld!\n", b, a);
            continue;
        }
        printf("%lld does not divide %lld!\n", b, a);
    }
    return 0;
}

please help me.
thanks.

[rhsumon]

Why run time error
I'll be mad for this problem
I also tried by making big array size
Here is my code:

Code: Select all

Now I changed code and now it is WA
Plz somebody help me
The code is:

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define P 50000

long prime[P]; 
long p[10000],f[10000];
int efact=0; 

void gen_prime(){
	int i,j;
	prime[0] = prime[1] = 1;
	for(i=2; i<=(long)sqrt(P); i++){
		if(prime[i]==0){ 
			for(j=i*i; j<=P-1; j=j+i){
				prime[j]=1;
			}
		}
	} 
	j=0; 
	for(i=0; i<=P-1; i++){ 
		if(prime[i] == 0){
			p[j] = i;
			f[j++]=0;
		}
	}
}

int matchfact(int fm, int num, int n){
	int sum;
	sum=0;
	while(n > 0){
		sum+=(n/fm);
		n/=fm;
		if(sum >= num) return 1;
	}
	return 0;
}

int find_fact(int m){
	int i;
	i=0;
	while(m!=1 && p[i]*p[i]<=m){
		while(m%p[i]==0){
			m/=p[i];
			f[i]++;
		}
		i++;
	}
	if (m>1) efact=m;
	return i;
}

int is_prime(int m){
	int i;
	if(m <= P){
		if(!prime[m]) return 1;
		else return 0;
	}
	else{
		for(i=0; p[i]<=(long)sqrt(m); i++){
			if(m%p[i]==0) return 0;
		}
	}
	return 1;
}
	

int main()
{
	//freopen("10139.out","w", stdout);
	int m,n,i,div,k;
	gen_prime();
	while(scanf("%d%d",&n,&m)==2){
		div=0;
		if(m==0) div=0;
		else if(n==0 || n==1){
			if(m==1) div=1;
			else div=0;
		}
		else if(m <= n) div=1;
		else if(is_prime(m)){
			div = matchfact(m,1,n);
		}
		else{
			k=find_fact(m);
			if(efact>0){
				div=matchfact(efact,1,n);
				efact=0;
				if(div == 0){
					printf("%d does not divide %d!\n",m,n);
					continue;
				}
			}
			for(i=0; i<k; i++){
				if(f[i]!=0){ 
					div=matchfact(p[i],f[i],n);
					f[i]=0;
					if(div == 0) break;
				}
			}
		}
		if(div == 0) printf("%d does not divide %d!\n",m,n);
		else printf("%d divides %d!\n",m,n);
	}

Plz help Somebody...

[Md. Mijanur Rahman]

/*
I am totally astonished, I got WA, Please anyone help to find out the reason
Here is my code:
*/
#include<stdio.h>
#include<string.h>
#include<math.h>

int main(){
long int i,k,len1,len2,M,N,n,temp,flag,half,s1,s2;
char a[100],b[100];


scanf("%ld",&n);

for(half=1;half<=n;half++)
{

scanf("%s %s",a,b);
len1=strlen(a);
len2=strlen(b);
temp=0;k=1;
for(i=len1-1;i>=0;i--)
{
temp+=(a-'0')*k;
k=k*2;
}
M=temp;
temp=0;k=1;
for(i=len2-1;i>=0;i--)
{
temp+=(b-'0')*k;
k=k*2;
}
N=temp;

if(M==N)
printf("Pair #%ld: All you need is love!\n",half);

else if(M>N){
flag=0;s1=sqrt(N);
for(k=2;k<=s1;k++)
if((M%k==0)&&(N%k==0))
{
flag=1;break;
}
if(flag==0)
printf("Pair #%ld: Love is not all you need!\n",half);
else
printf("Pair #%ld: All you need is love!\n",half);
}

else if(M<N){
flag=0;s2=sqrt(M);
for(k=2;k<=s2;k++)
if((M%k==0)&&(N%k==0))
{
flag=1;break;
}
if(flag=0)
printf("Pair #%ld: Love is not all you need!\n",half);
else
printf("Pair #%ld: All you need is love!\n",half);

}



}


//}
return 0;
}

[SAMEERAN]

i am getting wrong output for this following input case.
please help me
1233472 1233473

Code: Select all

#include<iostream>
using namespace std;

int main()
{
	//int n;d;
	unsigned long int temp_num,n,d;
	int flag;

	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
		while( scanf("%lu %lu",&n,&d)!=EOF)
		{
			if(n==0 && d==1)
			{
				printf("%lu divides %lu!\n",n,d);
				continue;
			}
			flag=0;

			temp_num=n;
			//n--;

			while(n!=0)
			{
				n--;
				if(temp_num%d == 0)
				{
					flag=1;
					break;
				}

				//flag=1;
				if(temp_num<d)
					temp_num=temp_num*n;
				else
					temp_num= ( temp_num%d ) * n;
			}
			if(flag==1)
				printf("%lu divides %lu!\n",n,d");
			else
				printf("%lu does not divide %lu!\n",n,d);
		}

	return 0;
}/code]

[mf]

Your program doesn't even compile.

You probably get wrong output because of integer overflow. 'unsigned long' is only a 32-bit integer (except for 64-bit systems, but UVa's compiler is not 64-bit.)

Anyway, your algorithm is too slow. You need to factorize d and for each its prime factor p, find how many times it divides n! (there's a simple formula: n/p + n/p^2 + n/p^3 + ...), and compare that with multiplicity of prime p in d's factorization.

[leonardoferrari]

My code is not working !
What might be the problem ?

Code: Select all

/* 
 * File:   main.cpp
 * Author: Leonardo
 *
 * Created on 29 de Abril de 2011, 14:44
 */

#include <stdlib.h>
#include <iostream>
#include <math.h>
#include <string.h>

using namespace std;

/*
 * 
 */

long long get_powers(long long n, long long p) {
    long long res = 0;
    for (long long power = p; power <= n; power *= p)
        res += n / power;
    return res;
}

void factor(long long n, long long vet[], int exp[], long long &count) {
    long long i, counter = 0;
    long long contaExp = 0;
    long long entrada = n;
    memset(vet, 0, sizeof (vet));
    memset(exp, 0, sizeof (exp));


    entrada = n;

    while (entrada % 2 == 0) {
        vet[counter] = 2;
        counter++;
        entrada /= 2;
        if (counter > 0) {
            exp[contaExp]++;
        }
    }

    if (counter > 0)
        contaExp++;

    for (i = 3; i <= sqrt(entrada) + 1; i += 2) {
        if (counter == 0 && entrada % i == 0) {
            vet[counter] = i;
            counter++;
        }
        while (n % i == 0) {
            if (counter > 0 && i != vet[counter - 1]) {
                vet[counter] = i;
                counter++;
                contaExp++;
            } else if (counter > 0 && i == vet[counter - 1]) {
                exp[contaExp]++;
            }
            entrada /= i;
        }
    }

    if (entrada > 1)
        vet[counter] = entrada;

    count = counter;
}

int main(int argc, char** argv) {

    long long n, m;
    bool divide;

    while (cin >> n >> m) {
        long long vet[50000], total = 0;
        int exp[5000];
        divide = true;

        if (total == 0 && n != 0)
            divide = false;
        else if (n == m && n != 0)
            divide = true;
        else if (m == 1 && n > 0)
            divide = true;
        else if (n == 0 && m != 1)
            divide = false;
        else {

            factor(m, vet, exp, total);

            for (long long i = 0; i < total; i++)
                if (get_powers(n, vet[i]) < exp[i]) {
                    divide = false;
                    break;
                }
        }

        if (divide) {
            cout << m << " divides " << n << "!" << endl;
        } else {
            cout << m << " does not divide " << n << "!" << endl;
        }
    }

    return 0;
}

Thanks

[Kaidul]

I have tested with all the test cases found here and compare with the result of UVA toolkit. Everything seems okay but I got WA. Please tell me what the wrong with my code ?

Code: Select all

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <climits>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>

using namespace std;

#define REP(i,n) for(__typeof(n) i=0; i<(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
typedef long long int64;
typedef unsigned long long ui64;
typedef long double d64;
#define READ(f) freopen(f, "r", stdin)
#define PI acos(-1.0)
#define INF (1<<30)
#define eps 1e-8
#define pb push_back
#define ppb pop_back


#define Set(a, s) memset(a, s, sizeof (a))
#define N 50000

bool mark [N];
vector <int> primeList;

void sieve ()
{
	Set (mark, true);
	mark [0] = mark [1] = false;

	for ( int i = 4; i < N; i += 2 )
	    mark [i] = false;

	for ( int i = 3; i * i <= N; i += 2 )
		if ( mark [i] )
		   for ( int j = i * i; j < N; j += 2 * i )
		       mark [j] = false;

	primeList.push_back (2);

	for ( int i = 3; i < N; i += 2 )
	     if ( mark [i] )
	        primeList.push_back (i);
}


int get_powers(int n, int p)
{
    int res = 0;
    for (int power = p ; power <= n ; power *= p)
        res += n/power;
    return res;
}

int main()
{
    sieve(); 
    int n,m;
    int save, count, prime;
    bool flag;
    queue < pair<int, int> > primeFact;
    while(cin>>n>>m) {

        if(!m) {
            cout<<m<<" does not divide "<<n<<"!\n";
            continue;
        }

        if ( n >= m ) {
            cout<<m<<" divides "<<n<<"!\n";
            continue;
        }


        save = m;
        flag = true;

        REP(i, primeList.size()) {
            prime = primeList[i];
            if(prime > save) break;
            count = 0;
            while( !(m % prime) ) {
                count++;
                m /= prime;
            }
            if(count) {
               if( get_powers(n, prime) < count ) {
                   flag = false;
                   break;
               }
            }
        }
        if( m > 50000 &&  get_powers(n, m) < 1 ) {
          flag = false;
        }
        if(flag) cout<<save<<" divides "<<n<<"!\n";
        else cout<<save<<" does not divide "<<n<<"!\n";
    }
    return EXIT_SUCCESS;
}

[brianfry713]

Input:

Code: Select all

693438499 355221797
1906961596 696861364
19277445 153071487
1425172043 789363934
80930472 437298538
1740169544 35954892
651889099 1644251134
991560556 1237769122
23968840 1435228070
972216318 1778665265
759648947 290337689
1618902352 825933580
84200033 646552153
144174116 1745525289
1121404194 1118652520
1845110473 1524552604
1162313484 903139544
2107203345 626383481
1339167 770158415
1710509156 1074423309
1500928636 1433671786
1762692431 518287262
1748120406 561969531
60528182 1099704375
1722784439 1275116578
1908449460 178824846
1464947718 761239903
547197086 1920846209
1361892664 1021262901
1253823570 1232158153
1123378130 612718962
1370382743 1713273872
1661616095 1376303733
90361519 1814322749
1580251060 1687130016
1042078747 555577997
2067397701 797281862
862518964 1653047096
2002428687 1961969948
854230711 958049589
66863711 342231826
1275266889 16460429
788491427 1214349084
1879819841 414896012
743426303 48375084
527637875 1180214405
424184027 1435734426
521220457 626340582
1642284192 547756449
1329187975 755769939
644168632 781437487
149364092 1765604515
1436042890 837062231
982965175 746813477
1902563916 373917092
1322432676 1166649798
1509437505 1403046038
1324158997 1885470454
894904730 47962041
1048281462 621560909
491540680 1798871230
588463555 1749672158
800273981 1386809697
1973657496 1126650229
913414945 2002285276
1502907130 2021392732
795653671 1949316691
1460702415 2051242694
133543725 1063771220
1328017183 209540592
1569530741 1394183105
885957060 582287000
1315272635 1840504788
468375553 1361426947
231695620 2084060820
755791181 848369516
1756037744 186358092
331052807 2065962976
1261213540 1578384495
499486980 101303371
1099116516 991634585
232490977 245966666
2138152519 885251946
313903496 1168420614
451206160 813058594
1075538440 561512693
1919286398 1468172611
1641450652 27416579
84478182 1854483858
1969104411 727538912
27244096 1086521199
823440149 807940603
365876929 64815989
39874533 1403945059
1987755822 1109306954
654235713 1955984084
395407348 802974548
1396565406 1660594022
1012116319 729325145
2109793327 446108018

AC output:

Code: Select all

355221797 divides 693438499!
696861364 divides 1906961596!
153071487 divides 19277445!
789363934 divides 1425172043!
437298538 divides 80930472!
35954892 divides 1740169544!
1644251134 divides 651889099!
1237769122 divides 991560556!
1435228070 divides 23968840!
1778665265 divides 972216318!
290337689 divides 759648947!
825933580 divides 1618902352!
646552153 divides 84200033!
1745525289 does not divide 144174116!
1118652520 divides 1121404194!
1524552604 divides 1845110473!
903139544 divides 1162313484!
626383481 divides 2107203345!
770158415 does not divide 1339167!
1074423309 divides 1710509156!
1433671786 divides 1500928636!
518287262 divides 1762692431!
561969531 divides 1748120406!
1099704375 divides 60528182!
1275116578 divides 1722784439!
178824846 divides 1908449460!
761239903 divides 1464947718!
1920846209 divides 547197086!
1021262901 divides 1361892664!
1232158153 divides 1253823570!
612718962 divides 1123378130!
1713273872 divides 1370382743!
1376303733 divides 1661616095!
1814322749 divides 90361519!
1687130016 divides 1580251060!
555577997 divides 1042078747!
797281862 divides 2067397701!
1653047096 divides 862518964!
1961969948 divides 2002428687!
958049589 divides 854230711!
342231826 divides 66863711!
16460429 divides 1275266889!
1214349084 divides 788491427!
414896012 divides 1879819841!
48375084 divides 743426303!
1180214405 divides 527637875!
1435734426 divides 424184027!
626340582 divides 521220457!
547756449 divides 1642284192!
755769939 divides 1329187975!
781437487 divides 644168632!
1765604515 does not divide 149364092!
837062231 divides 1436042890!
746813477 divides 982965175!
373917092 divides 1902563916!
1166649798 divides 1322432676!
1403046038 divides 1509437505!
1885470454 divides 1324158997!
47962041 divides 894904730!
621560909 divides 1048281462!
1798871230 divides 491540680!
1749672158 divides 588463555!
1386809697 divides 800273981!
1126650229 divides 1973657496!
2002285276 divides 913414945!
2021392732 divides 1502907130!
1949316691 divides 795653671!
2051242694 divides 1460702415!
1063771220 divides 133543725!
209540592 divides 1328017183!
1394183105 divides 1569530741!
582287000 divides 885957060!
1840504788 divides 1315272635!
1361426947 divides 468375553!
2084060820 divides 231695620!
848369516 divides 755791181!
186358092 divides 1756037744!
2065962976 divides 331052807!
1578384495 divides 1261213540!
101303371 divides 499486980!
991634585 divides 1099116516!
245966666 divides 232490977!
885251946 divides 2138152519!
1168420614 divides 313903496!
813058594 divides 451206160!
561512693 divides 1075538440!
1468172611 divides 1919286398!
27416579 divides 1641450652!
1854483858 does not divide 84478182!
727538912 divides 1969104411!
1086521199 divides 27244096!
807940603 divides 823440149!
64815989 divides 365876929!
1403945059 divides 39874533!
1109306954 divides 1987755822!
1955984084 divides 654235713!
802974548 divides 395407348!
1660594022 divides 1396565406!
729325145 divides 1012116319!
446108018 divides 2109793327!

[AhmadKhatar]

Hi!
I can't find the problem with my code!
Please help me!
Here is my code:

Code: Select all

#include <iostream>
#include <cmath>

using namespace std;

struct Factor
{
	int b, e;
}f [ 31 ];


int n, m ;

void process();

int main()
{
	while( cin >> n >> m )
	{
		if ( m == 0 )
		{
			cout << m << " does not divide " << n << "!" << endl;
		}
		else if ( n == 0 )
		{
			if ( m == 1 )
			{
				cout << m << " divides " << n << "!" << endl;
			}
			else
			{
				cout << m << " does not divide " << n << "!" << endl;
			}
		}
		else
		{
			process();
		}
	}

	return 0;
}

void process()
{
	int fCnt = 0;
	int power;
	
	int tNum = m;
	if ( tNum > 1 )
	{
		long long int i = 2;
		while( i * i <= tNum )
		{
			power = 0;
			if ( tNum % i == 0 )
			{
				while ( tNum % i == 0 )
				{ 
					power++;
					tNum /= i;
				}
				f[ fCnt ].b = i;
				f[ fCnt ].e = power;
				fCnt++;
			}

			if ( i == 2 )
			{
				i++;
			}
			else
			{
				i += 2;
			}
		}
		f[ fCnt ].b = tNum;
		f[ fCnt ].e = 1;
		fCnt++;
	}

	for ( int i = 0; i < fCnt; i++ )
	{
		double pw = 1;
		while ( f[ i ].e > 0 && pow( f[ i ].b, pw ) <= n )
		{
			f[ i ].e -= n / pow( f[ i ].b, pw );
			pw++;
		}
		if ( f[ i ].e > 0 )
		{
			cout << m << " does not divide " << n << "!" << endl;
			return;
		}
	}

	cout << m << " divides " << n << "!" << endl;
}

Thanks in advance!

[brianfry713]

Don't use floating point.