Help needed in CODE_03

Can someone explain the logic to this problem : https://www.codechef.com/COM12020/problems/CODE_03

I think that there are three special factors 2,3,5. Remove those from x and keep a count of them. Let us denote this new number by x_0. Let us also denote the largest power of i that divides x as p_i. We can find the smallest 999…000… type multiple by simulating long division of 1/x_0


You just need the length here, nothing else.
Then we can find the largest power of 2 and 5 which is equal to the number of 0s and the largest power of 3 is equal to 9*(length of nines)'s largest power.
Fun fact : the number of 0s will be 0 because we already removed 2 and 5.
We know that we can convert into our form by multiplying by 4/9. But we cannot always do that.first off we know the number of 0s will be max(p_2-2,p_5) Now we have a number of the form 999…000… . We can find now if the largest power of 3 that divides 999…000(calling it z_3) is lesser than p_3+2, we multiply i length of 9s by 3^{p_3-z_3+2}. now the length of 9s will be equal to length of 4s. so we can do 2*a + b on it directly.

1 Like

can you kindly explain what you are doing with an example, i am unable to understand it and also how 999…000… is coming into picture ??

I just searched it on the net, and apparently this isn’t common knowledge.
Basically, if a recurring decimal has a non recurring part of length b and a recurring part of length a, it can be written as x/(9999(atimes)00000(b times)

#include <iostream>
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
#define ll long long int
#define mp make_pair
#define pb push_back
#define vi vector<int>
using namespace std;
long long int p=1e9 +7;
long long int modpower(long long int b,long long po){
    long long int ans=1;
    while(po){
        if(po%2){
            ans*=b;
            ans%=p;
        }
        b*=b;
        b%=p;
        po/=2;
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	int t;
	cin >>t;
	while(t--){
	 int x;
	 cin>>x;
	 unordered_map<int,bool> point;
	 int num=10;
	 int decimal=1;
	 int a=0,b=0;
	 int x0=x;
	 int p3=0,p2=0,p5=0;
	 while(x0%2==0){
	     x0/=2;
	     p2++;
	 }
	 while(x0%3==0){
	     x0/=3;
	     p3++;
	 }
	 while(x0%5==0){
	     x0/=5;
	     p5++;
	 }
	 if(x0!=1){
	 while(true){
	     num=num%x0;
	     if(point[num]==0){
	       point[num]=1;
	     }
	     else{
	         a=decimal-1;
	         break;
	     }
	     num*=10;
	     decimal++;
	 }
	 }
	 else{
	 a=1;
	 }
     b=max(p2-2,p5);
     int z3=2;
     int k=a;
     while(k%3==0){
         k/=3;
         z3++;
     }
     if(z3-2<p3){
        a*=modpower(3,p3-z3+2);
     }
     cout<<2*a+b<<"\n";
	}
	
}

I’ve used the same variable names, see if you can understand.

1 Like

Oh right test cases
take x=2^2 * 5 * 3^4 *7
p2=2, p3=4,p5=1
x_0=7
The other 2 twos are required for 444 from 111.
b =max(p2-2,p5)=1
1/7=1.(428635)(428635)(428635)(428635)....
a=6.
so we get x_0|999999
Now append the 0s 9999990
Then find z_3=3 and we want to multiply by 4/9 so z_3 will become 1.
z_3>=p_3 otherwise x doesn’t divide our ans so we multiply our length by 27
so a=27*6 and b=1.
if you need the proof on why i can multiply by 3^3 then you can ask.

1 Like

Thanks for your effort bro, but i still can`t understand certain things.

  1. I got that first you are removing all the 2,3 and 5 from the number and then taking whatever you have.
  2. The number of zero is going to be determined by the max(p2-2,p5) so b is all set.
  3. I also got how a recurring decimal number can be represented as fraction with denominator of form 999…0…
  4. But like why are we taking x0(left out number after removing 2,3,5) as denominator and trying to gets it equivalent in 999…000…?
  5. 1/7 = 0.(142857)(142857)(142857)., and what is the logic behind z3.

would be grateful if you clarified

a mod b means remainder when a is divided by b.
ya ignore the 1/7, I didn’t feel like actually checking, but i knew the length was 6.
We are trying to get its equivalent and x_0 will divide it because it’s easy to calculate and gives you the smallest such number always.
z_3 is largest power of 3 that divides 999999, since we want to find 44444, we remove 2 from z_3(because we’re multiplying by 4/3^2) which has to be larger than p_3, otherwise it doesn’t divide it. if it isn’t then we have to multiply 3^{p3-z3}
Now to prove that we can multiply the length is trivial by induction.
We know 9 divides 9. To prove 27|999(27 divides 999) we can say 10 is 1 mod 9
so 9 = 90 = 900 mod 27 so 999 =3 * 9 mod 27 so it divides 27.
now 999 divides 27. 1000 is 1 mod 27. so 999= 999000=999000000 mod 81
which is all 27 or 27*2 mod 81. We don’t need to know which, because in either case we will need it 3 times.