Ссылка на проблему: Нули в конце (I) | LightOJ

Прежде всего, давайте рассмотрим факт: как мы преобразуем число с основанием 10 в число с основанием 2. Просто это. Мы должны делить число на 2, пока не получим частное = 0. Теперь мы попробуем преобразовать число 156 из 10 по основанию в 2.

Двоичное представление числа (156)10 будет (10011100)2. Первый остаток фактически представляет собой последнюю цифру. Нам нужно найти количество оснований при преобразовании из основания 10, будет хотя бы один конечный ноль. Для последней цифры должен быть ноль. Нам не нужно видеть остальных. Последняя цифра становится 0 только в том случае, если число N делится на основание.

На изображении мы видим, что мы получаем 0 в остатке только тогда, когда число N делится на основание. Только тогда мы сможем получить первый остаток равным 0. Итак, нам нужно узнать количество делителей N.

N всегда делится на 1. Но мы должны игнорировать это, так как вопрос требует от нас найти основание от 2 до бесконечности. Итак, мы должны уменьшить наш ответ на 1.

Чтобы решить задачу, нам нужно найти количество делителей, а затем уменьшить его на 1.

Мы знаем, что если простая факторизация числа N равна (p1)^e1*(p2)^e2⋯(pk)^ek, где pi — различные простые числа, то число делителей равно:

d(n)=(e1+1)*(e2+1)⋯(ek+1)

Итак, ответ будет d(n)-1.

Решение проблемы:

#include <bits/stdc++.h>
using namespace std;
#define m 1000010
long long int primes[m], cnt, siv[m];
void sieve()
{
    long long int i, j;
    for (i=3; i<m; i+=2)
        if(!siv[i])
            for (j=i*i; j<m; j+=i+i)
                siv[j]=1;
    primes[cnt++]=2;
    for (i=3; i<m; i+=2)
        if(!siv[i]) primes[cnt++]=i;
    return;
}
int main()
{
    sieve();
    long long int t,c=0;
    scanf("%lld",&t);
    while(t--)
    {
        long long int n,sum=1,s,k,i;
        scanf("%lld",&n);
// finding the number of divisors of N
        for(i=0;i<m && primes[i]*primes[i]<=n;i++)
        {
            if(n%primes[i]==0)
            {
                k=0;
                while(n%primes[i]==0)
                {
                    n/=primes[i];
                    k++;
                    if(n==0 || n==1)
                        break;
                }
                sum*=k+1;
            }
     }
/* if the number N is divided by some prime number than
   sum has to be multiped by (1+1) where first 1 is the count of
   that prime number, N is divisible by and second 1 is the plus one
   of the formula. */
     if(n!=1)
        sum*=2;
     printf("Case %lld: %lld\n",++c,sum-1);
    }
    return 0;
}