Q10083: Division (20点) 这题我有ＰＯ到知识家上： http://tw.knowledge.yahoo.com/question/question?qid=1508112308491 给你3个正整数 t,a,b（0 < t,a,b <= 2147483647），请你计算 ( t^a - 1) / (t^b - 1)。如果答案是小於100位数的整数，请输出答案。否则请输出 "is not an integer with less than 100 digits."。 Input 每组测试资料一列，含有3个正整数 t、a、b。 Output 每组测试资料输出一列，如题目所述，格式请参考Sample Output。 Sample Input 2 9 3 2 3 2 21 42 7 123 911 1 Sample Output (2^9-1)/(2^3-1) 73 (2^3-1)/(2^2-1) is not an integer with less than 100 digits. (21^42-1)/(21^7-1) 18952884496956715554550978627384117011154680106 (123^911-1)/(123^1-1) is not an integer with less than 100 digits. --------------------------------------------------------------------------------------- 这题的重点是再,除数也就是分母也大於可以直接除的范围 假设一个很大的被除数跟小小的除数 例如: 123123123123123123/123456 可以分割成 (123/123456)x 100000000000000 + (123/123456) x 1000000000000 ...... 可是这题的分母与分子都大余可以用内建程式除的上限 可能这题有一些技巧 因为他是 (t^a-1) / (t^b-1) 若a=2的话 平方公式就是 (t+1)(t-1) = (t^2-1) Q1:那无限呢? 若题目是输入除数和被除数都非常大 (这只是假设) 被除数 120000000000000 除数 1200000000 被除数可以拆成 (1200/1200)x(1000/1000)x(1000/1000)x1000x100 若被除数 21569874135145679246568947894654....... 除数 5645123487896456489421321.... 这种找因式的方法可能就跑不出来了 而一直相减的暴力法就更不用说了... (大数相除 *除数和被除数都溢位) Q2:不知道有大大有什麽好方法可以提供^^???? (VB6.0程式码或者演算法都OK=ˇ=") -分割线--刚刚自己想出来的方法--------------------------- 用相乘and相减 找个位数 这三个重点 破解一组答案 先新增一个空白s="" (这是一组小算盘可以计算的数字) 假设 t^a-1=304696744428557889118768=a t^b-1=4654954984844849=b 两个相除的结果=65456432=c 至於怎麽推到答案 a/b = c = 65456432 首先 看尾数 b的尾数=9 9*多少=a的尾数8 对乘2=18 把a-b整项*2 304696744428557889118768 - 4654954984844849*2 ------------------------- 304696735118647919429070 因为已经求到一位 2 所以把 0消掉(消掉一位) 304696735118647919429070/10 此时 a =30469673511864791942907 s= 2 & s 继续 b的尾数=9 9*多少=a的尾数7 对乘3=27 把a-b整项*3 30469673511864791942907 - 4654954984844849*3 ------------------------ 30469659546999837408360 求到一位 3 所以把 0 消掉 a又变成了 3046965954699983740836 此时 s= 3 & s s 内容 = 32 以此类推 最後结果可以推到65456432 ＜使用程式ＶＢ６＞ 不知道有没有其他更好更快速的解法？ 或是　这题的正统解法？？ -- ※性别：男　 ※生日：1990/05/08 ※星座：金牛座　 ※血型：Ａ　 ※我的无名；http://www.wretch.cc/blog/tomas0011 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.130.37.170