10139 - Factovisors

[AhmadKhatar]

Thanks!
It worked!

[vsha041]

My code was passing all test cases until I found this test case:

6664 429470327

The answer here is Yes it divides because the prime factors of 429470327 are 11^1 * 13^1 * 1733^2. Now obviously 6664! contains 11 and 13 in it but my code was doing it in the following way.

For 6664!, I was calculating all the prime factors up until square root of 6664. Now when I saw 1733, I just checked if 1733's power is 1 or not and if it is less than 6664! then it is divisible but in this case that's wrong and it will say it is not divisible as power of 1733 is 2. The correct way is to check if power of 1733 is less than or equal to 6664/1733 or not. Then since this is true, it will give correct answer.

[frimlik]

Hey guys,

I wonder, where is a mistake in my code... All inputs found here and also those sample have been tried and all outputs seem to be ok, but there is still a mistake somewhere... UVA shows me always WA...

Code: Select all

Removec after getting AC

[brianfry713]

Try solving it without using floating point.

[Tahanima]

Can anyone please help me out to find out why am I getting wrong answer with this code?

Code: Select all

#include <stdio.h>
#include <map>
#include <iterator>
using namespace std;

int main() {
    long long n,m,temp;
    while(scanf("%llu %llu", &n, &m) == 2){
        temp = m;
        map<long long,int> div;
        for(long long i = 2; i*i<=m && m!=1; i++){
            while(m%i == 0){
                if(!div.count(i)){
                  div[i] = 1;    
                }
                else{
                    div[i]++;
                }
                m/=i;
            }
        }
        if(m>1){
            div[m] = 1;
        }
        
        int res = 0;
        map<long long,int>:: iterator itr;
        for(itr = div.begin(); itr!= div.end(); itr++){
            long long divisor = (*itr).first; int freq = (*itr).second;
            res = 0;
            while(n/divisor > 0){
                res+=(n/divisor);
                divisor*=divisor;
            }
            if(res == 0 || res<freq){
                res = 0;
                break;
            }
        }
        
        if(res == 0 && temp!=1){
            printf("%llu does not divide %llu!\n", temp, n);
        }
        else{
            printf("%llu divides %llu!\n", temp, n);
        }
    }
    return 0;
}

[maddi]

I have checked with all available inputs,but still getting WA.Please help me out,what is wrong with my code?

Code: Select all

#ifndef HEADER_H
#define HEADER_H
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<algorithm>
#include<stack>
#include<ctype.h>
#include<cstdlib>

#define F(t,i,s,r) for(t i=s;i<r;i++)
#define FE(t,i,s,r) for(t i=s;i<=r;i++)
#define R(t,i,s,r) for(t i=s;i>r;i--)
#define RE(t,i,s,r) for(t i=s;i>=r;i--)

using namespace std;
//freopen("i.txt", "r", stdin);
//freopen("o.txt","w",stdout);
#endif
#define ll long long
ll primePowInFacto (ll n,ll p) {
	ll res = 0;
	for (ll pow = p; pow <= n;pow*=p) {
		res += n/pow;
	}
	return res;
}
bool primediv (ll a,ll b) {
	if (a == 0||((b==0||b==1)&&a!=1))return false;
	else if (a == 1)return true;
	else {
		ll n = a, c, pc;
		for (ll i = 2; i*i <= a; i++) {
			c = 0;
			while (n > 1 && n%i == 0)
			{
				c++;
				n /= i;
			}
			if (c > 1) {
				pc = primePowInFacto (b, i);
				if (pc < c) { return false; }
			}
		}
		if (n > 1) {
			c = 1;
			pc = primePowInFacto (b, n);
			if (pc < c)return false;
		}
		return true;
	}
}
int main () {
	ll a, b;
	while (cin>>a>>b)
	{
			if (primediv (b, a)) {
				printf ("%lld divides %lld!\n", b, a);
			}
			else {
				printf ("%lld does not divide %lld!\n", b, a);
			}
		}
}