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

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

12090 - Counting Zeroes

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

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