trungdovan87 I get 100/100 point :)
Solution:
- Call it as Ab (e.g: if 2345 -> A = 234 and b = 5), and Ab have n length
We need to resolve: Ab * x = bA
=> A = {b[10^(n-1) - x]} / (10x - 1)
(I will explain later)
with:
- x = 1 to 9 - n = 2 to m - b = 1 to 9 - length of A is equal to (n-1)- We can find A with above conditions. And in Java, we use BigInteger to calculate.
explain:
Ab * x = bA => (10A + b) * x = b * (10^(n-1)) + A => 10x * A + b * x = b * (10^(n-1)) + A => (10x - 1) A = b[ 10^(n-1) - x] => A = {b[10^(n-1) - x]} / (10x - 1)
akash_42414241 amazing!!
mini_weblab Agreed! :)
israellaks amazing!!! great job!!!
NourSamir it's an amazing solution, literally so creative one. How this solution inspired ?, i mean which theorem inspired you ?
trungdovan87 Please, remember in project Euler that "more calculation of human, less calculation of Computer"
Ryo112358 Could someone explain how the above algorithm to calculate A can be used as an alternative to brute force? From what I understand, we don't know the b or the x, so wouldn't we still have a ton of iterations to do regardless? Here's my current approach (brute force):
'''java
for(BigInteger i = ten; i.compareTo(upperLimit) != 1; i = i.add(one)) { rotated = rotateRight(i); if(rotated.mod(i).compareTo(zero) == 0) divisible.add(i); } System.out.println(lastFiveDigits(addElements(divisible)));
'''
Edit: Never mind! Not there yet but getting close...
coolchand5725 Nailed it bro
ankits5652 This is not clear by last 5 digits...
shubham20_yeole yes. that part was confusing for me too.
wshanshan It was not clear.
Here is what it means (after trials and errors):
- sumVal = sum (all the numbers in the range that have the property)
- return sumVal mod 100000
shubham20_yeole hmm that makes sense
Marco_L_T #include<stdio.h> int a[105]={0,0,495,5490,55485,55480,98331,98326,98321,98316,98311,98306,41157,75329,75324,75319,75314,75309,28684,28679,28674,28669,19968,19963,62814,62809,96981,96976,90073,90068,32919,32914,32909,32904,32899,32894,86269,86264,86259,20431,20426,20421,34700,34695,50713,50708,50703,50698,93549,93544,93539,93534,27706,27701,81076,81071,74168,74163,63988,63983,6834,6829,6824,6819,6814,40986,75141,75136,75131,75126,75121,75116,28491,28486,28481,28476,28471,28466,5494,5489,5484,5479,5474,5469,12850,12845,12840,12835,28853,28848,82223,16395,16390,16385,16380,16375,59226,59221,59216,59211,59206}; int main (){ int m; scanf ("%d",&m); printf ("%d\n",a[m]); return 0; }
I made a list and successfully passed the tests. You can check the correctness of your code through the list.
rkmr039 [deleted]
khoangcachxalam1 thank for your good idea (name's you : #trungdovan87 ) and your result ! i wrestle with some errors in myself code , then i run code and save result into a textbox , finally , i only println it ! with n=109 result=89574 ! n=108 result =89579 !
me_anujj how you had made this list ?
rishavrahul1361 how you creater this list
kalok87 What is test-case 7? Only cannot get it right, weird...
ivan_vranjic [deleted]ivan_vranjic Had the same problem. Answer must not have leading zeros. Printing answer modulo 10^5 instead of printing last 5 digits did it for me. Badly formulated desired output.
anugrahsaxena It says m < 100. So, for very large value of m say m=99, n will belong to values between 10 and 1e99. How are you guys dealing with the bigInteger?
For me, some easy test cases are passing but others are giving time out!
Sort 40 Discussions, By:
Please Login in order to post a comment