12090 - Counting Zeroes

[Ahmed_Salama]

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]

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