10139 - Factovisors

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 10139 - Factovisors

Thanks!
It worked! vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 10139 - Factovisors

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
New poster
Posts: 3
Joined: Sat Oct 04, 2014 11:14 pm

Re: 10139 - Factovisors

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
Last edited by frimlik on Tue Jan 13, 2015 11:19 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10139 - Factovisors

Try solving it without using floating point.
Check input and AC output for thousands of problems on uDebug!

Tahanima
New poster
Posts: 8
Joined: Thu Dec 25, 2014 4:50 pm

Re: 10139 - Factovisors

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;
}

New poster
Posts: 6
Joined: Sat Jun 07, 2014 12:07 am

Re: 10139 - Factovisors

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

Code: Select all

#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);
}
}
}