Project Euler 284

题目

Steady Squares

The $3$-digit number $376$ in the decimal numbering system is an example of numbers with the special property that its square ends with the same digits: $376^2 = 141376$. Let’s call a number with this property a steady square.

Steady squares can also be observed in other numbering systems. In the base $14$ numbering system, the $3$-digit number $c37$ is also a steady square: $c37^2 = aa0c37$, and the sum of its digits is $c+3+7=18$ in the same numbering system. The letters $a, b, c$ and $d$ are used for the $10, 11, 12$ and $13$ digits respectively, in a manner similar to the hexadecimal numbering system.

For $1 \le n \le 9$, the sum of the digits of all the $n$-digit steady squares in the base $14$ numbering system is $2d8$ ($582$ decimal). Steady squares with leading $0$’s are not allowed.

Find the sum of the digits of all the n-digit steady squares in the base $14$ numbering system for $1 \le n \le 10000$ (decimal) and give your answer in the base $14$ system using lower case letters where necessary.

解决方案

不难发现，如果一个$n$位$14$进制数是满足题意，那么它满足以下方程：

$$a^2\equiv a\pmod {14^n}$$

可以将其重新写成$a^2-a\equiv0\pmod {14^n}$。并且，方程的两个解$x_n,y_n$将会满足$x_n+y_n=14^n+1$，并且两个解的个位分别为$7$和$8$。因此，一对解中，除了其最低位之和为$15$，所有的对应位之和为$13$。根据中国剩余定理，不失一般性，假设$x_n\equiv 1\pmod {2^n},x_n\equiv0\pmod {7^n}$。

通过进一步打表可以发现，在方程$a^2-a\equiv0\pmod {14^n}$的两个解的最高位中再添加一位，即可变成方程$a^2-a\equiv0 \pmod {14^{n+1}}$的解$x{n+1},y{n+1}$。

令这个数位为$d$。那么令$x{n+1}=14^nd + x_n$，并且有$x{n+1}^2\equiv x_{n+1}\pmod {14^{n+1}}$

联立后，得到$14^{2n}d^2+2\cdot 14^nd\cdot x_n+x_n^2\equiv14^nd+x_n\pmod {14^{n+1}}$

最终，左边第一项明显是$14^{n+1}$的倍数；对于第二项，由于$x_n\equiv0\pmod {7^n}$，因此第二项也是$14^{n+1}$的倍数。

因此，方程最终化成：

$$d\equiv\dfrac{x_n^2-x_n}{14^n}\pmod {14}$$

因此将计算出的$d$拼接在$xn$的最高位，形成$x{n+1}$。

最终直接统计即可。

代码

本题使用了GMP库进行大整数运算。

#include <bits/stdc++.h>
#include<gmpxx.h>
using namespace std;
typedef long long ll;


const int N=10000,B=14;
string to_B(mpz_class a){
    string s;
    for(;a;a/=B){
        mpz_class b=a.get_si()%B;
        int x=b.get_si();
        if(x<10) s+=char('0'+x);
        else s+=char('a'+x-10);
    }
    reverse(s.begin(),s.end());
    return s;
}
int f(int now){
    int ans=1;
    int d=now,s=0;
    mpz_class x=0,pw=1,t;
    for(int n=1;n<=N;n++){
        s+=d;
        if(d==0) ans+=n*(B-1)+2-s;
        else if(d==B-1) ans+=s;
        else ans+=n*(B-1)+2;
        x+=pw*d;pw*=B;
        t=x*(x-1)/pw%B;
        d=t.get_si();
    }
    return ans;
}
int main() {
    string ans=to_B(f(B/2));
    cout<<ans<<endl;
}