文章目录
  1. 1. 原题
  2. 2. 分析
  3. 3. 递推算法实现
  4. 4. 解决问题
    1. 4.1. 输出
  5. 5. 小结

Project Euler Problem 455 - Powers With Trailing Digits ,Completed on 2015-10-10 00:50

原题

Let f(n) be the largest positive integer x less than 109 such that the last 9 digits of nx form the number x (including leading zeros), or zero if no such integer exists.

For example:

  • f(4) = 411728896 (4411728896 = …490411728896)
  • f(10) = 0
  • f(157) = 743757 (157743757 = …567000743757)
  • Σf(n), 2 ≤ n ≤ 103 = 442530011399
    Find Σf(n), 2 ≤ n ≤ 106.

分析

设 f(n) = x,根据题意可得:
nx≡x(mod 109)
也就是x满足:
x = powerMod(n,x,109) [1]
所以,为了求f(n)的值x,可以用穷举试探法,从 x = 0开始试探,直到找到满足[1]的x,或者x变成0;x每次递归取值为:
xk+1 = powerMod(n, xk, 109);
终止条件是:
xk+1 = xk or xk+1=0

递推算法实现

/**
* 求f(n) = x,满足:
* (1), n^x % 10^9 = x; or
* (2),x=0 如果不存在满足(1)的x
*/

public static long f(int n) {
long m = (long) Math.pow(10, 9);
long k = 0;
while (true) {
long x = powerMod(n, k, m);
if (x == 0) {
return 0;
}
if (k == x && x > 0) {
return x;
}
k = x;
}
}

powerMod是幂模运算的快速算法,参见蒙哥马利(Montgomery)幂模运算

解决问题

从i=2到109遍历相加f(i)得到结果:

/**
* 求f(n) = x,满足:
* (1), n^x % 10^9 = x; or
* (2),x=0 如果不存在满足(1)的x
*/

public static long f(int n) {
long m = (long) Math.pow(10, 9);
long k = 0;
while (true) {
long x = Util.powerMod(n, k, m);
if (k == x || x == 0) {
return x;
}
k = x;
}
}

输出

450186511399999
Time consumed : 983 ms

小结

这个题目也用到了快速幂模运算,求解f(n),理解f(n)=x对x进行迭代是解决问题的关键。

文章目录
  1. 1. 原题
  2. 2. 分析
  3. 3. 递推算法实现
  4. 4. 解决问题
    1. 4.1. 输出
  5. 5. 小结