HackerRank Number Theory – A Very Special Multiple

Challenge: A Very Special Multiple

Subdomeniu: Number Theory (number-theory)

Scor cont: 80.0 / 80

Submission status: Accepted

Submission score: 1.0

Submission ID: 464745850

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/a-very-special-multiple/problem

Cerinta

Charlie and Johnny play a game. For every integer $X$ Charlie gives, Johnny has to find the smallest positive integer $Y$ such that $X \times Y$ ($X$ multiplied by $Y$) contains only 4s and 0s and starts with one or more 4s followed by zero or more 0s. For example, 404 is an invalid number but 4400, 440, and 444 are valid numbers. 

If $a$ is the number of 4s and $b$ is the number of 0s, can you print the value of $(2\times a) + b$?  

**Input Format**  

The first line of input contains a single integer $T$, the number of test cases.  

$T$ lines follow, each line containing the integer $X$ as stated above.

**Output Format**  

For every $X$, print the output $(2\times a) + b$ in a newline as stated in the problem statement.  

**Constraints**  

$1 \le T \le 100$  
$1 \le X \le 10^{10}$  

**Sample Input**  
 
    3
    4
    5
    80

**Sample Output**  
 
    2
    3
    4

**Explanation**  

For the 1<sup>st</sup> test case, the smallest such multiple of $4$ is 4 itself. Hence the value of $a$ will be $1$ and and the value of $b$ will be $0$, and the answer is $(2\times a) + b = 2$.  

For the 2<sup>nd</sup> test case, $Y = 8$ and 40 is the minimum such multiple of $5$. Hence the values of $a$, $b$ and $(2 \times a) + b$ will be $1$, $1$ and $3$ respectively.

Cod sursa

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
void getp(long long N,long long*prim);
unsigned long long modPow(unsigned long long a,unsigned long long x,unsigned long long mod);
long long get_phi(long long N,long long *prime);
void solve(int count,int* c,int* rp,long long pp,long long x);
long long bigmm(long long a,long long b,long long mod);
long long a;

int main(){
  int T,count,*rp,*c,i,j;
  long long x,b,*p,*lcd,P,lcm;
  rp=(int*)malloc(80*sizeof(int));
  c=(int*)malloc(80*sizeof(int));
  p=(long long*)malloc(1000000*sizeof(long long));
  lcd=(long long*)malloc(80*sizeof(long long));
  getp(1000000,p);
  scanf("%d",&T);
  while(T--){
    a=((long long)1)<<60;
    scanf("%lld",&x);
    b=0;
    if(x%2==0)
      x/=2;
    if(x%2==0)
      x/=2;
    while(x%10==0){
      b++;
      x/=10;
    }
    while(x%2==0){
      b++;
      x/=2;
    }
    while(x%5==0){
      b++;
      x/=5;
    }
    count=0;
    lcm=x;
    x=get_phi(9*x,p);
    for(i=0;p[i];i++)
      if(x%p[i]==0){
        rp[count]=p[i];
        c[count]=0;
        while(x%p[i]==0){
          x/=p[i];
          c[count]++;
        }
        count++;
      }
    if(x!=1){
      rp[count]=x;
      c[count]=1;
      count++;
    }
    solve(count,c,rp,1,lcm*9);
    printf("%lld\n",2*a+b);
  }
  return 0;
}
void getp(long long N,long long*prim){
  long long i,j,index=2,flag;
  if(N<=1){
    prim[0]=0;
    return;}
  if(N==2){
  prim[0]=2;
  prim[1]=0;
  return;}
  prim[0]=2;
  prim[1]=3;
  for(i=5;i<=N;i=i+2)
    {
      for(j=1,flag=1;prim[j]<=sqrt(i);j++)
        {
          if(i%prim[j]==0){
            flag=0;
            break;}
        }
      if(flag==1)
        {prim[index]=i;
          index++;}
    }
  prim[index]=0;
  return;
}
unsigned long long modPow(unsigned long long a,unsigned long long x,unsigned long long mod){
  unsigned long long res = 1;
  while(x>0){
    if(x%2)
      res=bigmm(a,res,mod);
    a=bigmm(a,a,mod);
    x>>=1;
  }
  return res;
}
long long get_phi(long long N,long long *prime){
  long long ans=N,i;
  for(i=0;prime[i]*prime[i]<=N && prime[i];i++)
    if(N%prime[i]==0){
      while(N%prime[i]==0)
        N/=prime[i] ;
      ans=ans-ans/prime[i];
    }
  if(N>1)
    ans=ans/N*(N-1);
  return ans;
}
void solve(int count,int* c,int* rp,long long pp,long long x){
  int i;
  if(count==0){
    if(modPow(10,pp,x)==1 && pp<a)
      a=pp;
    return;
  }
  solve(count-1,c+1,rp+1,pp,x);
  for(i=0;i<c[0];i++){
    pp*=rp[0];
    solve(count-1,c+1,rp+1,pp,x);
  }
  return;
}
long long bigmm(long long a,long long b,long long mod){
  int ar[20],size=0,i,j;
  long long ans=0,temp;
  for(i=0;b;i++){
    ar[i]=b%10;
    size++;
    b/=10;
  }
  for(i=0;i<size;i++){
    temp=ar[i]*a%mod;
    for(j=0;j<i;j++)
      temp=temp*10%mod;
    ans=(ans+temp)%mod;
  }
  return ans;
}