CF1916D Mathematical Problem

· · 个人记录

神秘题。

样例瞪不出任何规律，考虑打表。

打表出 n\leq 15 的最小可行解，如下：

...
11
10002400144 100012
10004200441 100021
10020410404 100102
10024014400 100120
10040240401 100201
10042044100 100210
10201404004 101002
10241440000 101200
10404204001 102001
10424410000 102100
12100440004 110002
13
1000024000144 1000012
1000042000441 1000021
1000204010404 1000102
1000240014400 1000120
1000402040401 1000201
1000420044100 1000210
1002041040400 1001020
1002401440000 1001200
1004024040100 1002010
1004204410000 1002100
1020104040004 1010002
1020140400400 1010020
1024144000000 1012000
15
100000240000144 10000012
100000420000441 10000021
100002040010404 10000102
100002400014400 10000120
100004020040401 10000201
100004200044100 10000210
100020041004004 10001002
100020401040400 10001020
100024001440000 10001200
100040024004001 10002001
100040204040100 10002010
100042004410000 10002100
100200140040004 10010002
100204104040000 10010200
100240144000000 10012000

其中，n\leq 9 没有任何规律。

在 n\geq 11 时，最小可行解的平方根由两个 1，一个 2 和若干个 0 组成。

发现有一个 1 固定在最高位。那么这些数可以表示为 10^{\lceil\frac{n}{2}\rceil}+10^i+2\times 10^j(i\neq j)。

那么暴力枚举 i,j，然后做高精度乘法即可。

时间复杂度 O(n^3)。

//Man always remember love because of romance only!
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int X=0,w=0; char ch=0;
    while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
    while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
inline void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int n;
map<multiset<int>,int> mp;
int a[10001],b[10001],c[10001];
int len;
void work(){
    reverse(a+1,a+len+1);
    for(int i=1;i<=len;i++) b[i]=a[i];
    for(int i=1;i<=2*len;i++) c[i]=0;
    for(int i=1;i<=len;i++)
        for(int j=1;j<=len;j++) c[i+j-1]+=a[j]*b[i];
    for(int i=1;i<len+len;i++)
        while(c[i]>9){
            c[i+1]++;
            c[i]-=10; 
        }
    len=len+len;  
    while(c[len]==0&&len>1) len--;
}
int tp[1001]={0,12,21,102,120,201,210,1002,1020,1200,2001,2010,2100,10002,10020,10200,12000,20001,20010,20100,21000,100002,100020,100200,102000,120000,200001,200010,200100,201000,210000,1000002,1000020,1000200,1002000,1020000,1200000,2000001,2000010,2000100,2001000,2010000,2100000,10000002,10000020,10000200,10002000,10020000,10200000,12000000,20000001,20000010,20000100,20001000,20010000,20100000,21000000,100000002,100000020,100000200,100002000,100020000,100200000,102000000,120000000,200000001,200000010,200000100,200001000,200010000,200100000,201000000,210000000,1000000002,1000000020,1000000200,1000002000,1000020000,1000200000,1002000000,1020000000,1200000000,2000000001,2000000010,2000000100,2000001000,2000010000,2000100000,2001000000,2010000000,2100000000,10000000002,10000000020,10000000200,10000002000,10000020000,10000200000,10002000000,10020000000,10200000000,12000000000,20000000001,20000000010,20000000100,20000001000,20000010000,20000100000,20001000000,20010000000,20100000000,21000000000,100000000002,100000000020,100000000200,100000002000,100000020000,100000200000,100002000000,100020000000,100200000000,102000000000,120000000000,200000000001,200000000010,200000000100,200000001000,200000010000,200000100000,200001000000,200010000000,200100000000,201000000000,210000000000,1000000000002,1000000000020,1000000000200,1000000002000,1000000020000,1000000200000,1000002000000,1000020000000,1000200000000,1002000000000,1020000000000,1200000000000,2000000000001,2000000000010,2000000000100,2000000001000,2000000010000,2000000100000,2000001000000,2000010000000,2000100000000,2001000000000,2010000000000,2100000000000,10000000000002,10000000000020,10000000000200,10000000002000,10000000020000,10000000200000,10000002000000,10000020000000,10000200000000,10002000000000,10020000000000,10200000000000,12000000000000,20000000000001,20000000000010,20000000000100,20000000001000,20000000010000,20000000100000,20000001000000,20000010000000,20000100000000,20001000000000,20010000000000,20100000000000,21000000000000,100000000000002,100000000000020,100000000000200,100000000002000,100000000020000,100000000200000,100000002000000,100000020000000,100000200000000,100002000000000,100020000000000,100200000000000,102000000000000,120000000000000,200000000000001,200000000000010,200000000000100,200000000001000,200000000010000,200000000100000,200000001000000,200000010000000,200000100000000,200001000000000,200010000000000,200100000000000,201000000000000,210000000000000};
signed main(){
    int T=read();
    while(T--){
        n=read();
        if(n<=17){
            mp.clear();
            for(int i=sqrt(pow(10,n-1));i*i<pow(10,n);i++){
                if(i*i<pow(10,n-1)) continue;
                int x=i*i;
                multiset<int> now;
                now.clear();
                while(x){
                    now.insert(x%10);
                    x/=10;
                } 
                mp[now]++;
                if(mp[now]==n){
                    int cnt=0;
                    for(int i=sqrt(pow(10,n-1));i*i<pow(10,n);i++){
                        if(cnt==n) break;
                        if(i*i<pow(10,n-1)) continue;
                        int x=i*i;
                        multiset<int> now1;
                        now1.clear();
                        while(x){
                            now1.insert(x%10);
                            x/=10;
                        } 
                        if(now1==now){
                            cout<<i*i<<" "<<i<<endl;
                            cnt++;
                        }
                    }
                    break;
                }
            }
        }else{
            int xx=n/2+1;
            len=xx;
            a[1]=0;
            for(int i=2;i<=len;i++) a[i]=0;
            for(int i=1;i<=n;i++){
                len=xx;
                a[1]=1;
                for(int j=2;j<=len;j++) a[j]=0;
                int tt=tp[i],tot=0;
                while(tt){
                    a[len-tot]=tt%10;
                    tt/=10;
                    tot++;
                }
//              for(int j=1;j<=len;j++) cout<<a[j]<<" ";
//              puts("");
                work();
                bool flag=1;
                for(int j=1;j<=len;j++){
                    if(c[j]!=1&&c[j]!=2&&c[j]!=4&&c[j]!=0){
                        flag=0;
                        break;
                    }
                }
                if(!flag){
                    n++;
                }else{
                    for(int j=len;j;j--) cout<<c[j];
                    puts("");
                }
            }

        }
    }
    return 0;
}