Can someone explain the logic to this problem : CodeChef: Practical coding for everyone
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.
- I got that first you are removing all the 2,3 and 5 from the number and then taking whatever you have.
- The number of zero is going to be determined by the max(p2-2,p5) so b is all set.
- I also got how a recurring decimal number can be represented as fraction with denominator of form 999…0…
- 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…?
- 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.