12090 - Counting Zeroes

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

Moderator: Board moderators

Post Reply
Ahmed_Salama
New poster
Posts: 1
Joined: Fri Nov 25, 2011 1:23 pm

12090 - Counting Zeroes

Post by Ahmed_Salama » Fri Nov 25, 2011 1:27 pm

I'm getting TLE.

I simply looped on all the factors of N. and with each one I count the number of trailing zeros in O(log_factor(N))

Code: Select all

#include <iostream>
#include <stdio.h>

using namespace std;

long long count(long long x, long long d) {
	long long cnt = 0;

	while(x > 0){
		if(x % d == 0)cnt++;
		else break;

		x /= d;
	}
	return cnt;
}


int main(){
	long long x;
	while(true){
		scanf("%lld", &x);
		if(x == 0)break;

		long long cnt = 0;

		for(long long d = 1; d * d <= x; d++)if(x % d == 0){
			if(d != 1) cnt += count(x, d);
			if(d * d != x) cnt += count(x, x / d);
		}

		printf("%lld\n", cnt);
	}
}
Here's a code snipt.

Thanks a lot.

vaxim
New poster
Posts: 2
Joined: Thu Sep 10, 2015 4:27 am

Re: 12090 - Counting Zeroes

Post by vaxim » Thu Sep 10, 2015 4:37 am

At first I got TLE too, later I factor using all primes less than 3170000 then got AC.

Post Reply

Return to “Volume 120 (12000-12099)”