CF1916D Mathematical Problem

One_JuRuo · 2023-12-31 13:07:29 · 题解

思路

很不错的人类智慧题。

拿到以后，完全没有思路，看到数据范围，感觉是什么 n^2\log n 的逆天做法，但是又完全没思路，看后面的题感觉没希望，就在这道题死磕。

先打了个暴力程序，发现平方数太多，没什么规律，就拿了个 map 统计一下那些出现数字方案拥有的平方数比较多

程序如下：

#include<bits/stdc++.h>
using namespace std;
multiset<int>s;
map<multiset<int>,int>mp;
int main()
{
    for(int i=1;i<=200000;++i)
    {
        long long k=1ll*i*i;
        if(k<100000000) continue;//此程序是九位数的情况，想试其他情况的就改这里的值即可
        if(k>999999999) break;
        while(k) s.insert(k%10),k/=10;
        ++mp[s],s.clear();
    }
    for(auto i:mp)
    {
        if(i.second>=9)//这里也要改
        {
            for(auto j:i.first)
            {
                cout<<j<<" ";
            }
            puts("");
        }
    }
    return 0;
}

先试一试五位数的情况，发现下面的数字组合都可以存在五个以上的平方数，除了样例给的还有一组。

0 0 1 6 9
1 3 4 6 8

再试一试七位数的情况，发现符合条件的数字组合更多了。

0 0 0 0 1 6 9
0 0 1 3 4 6 8
0 1 2 4 5 6 9
0 1 4 5 6 7 8
1 2 3 4 4 5 6
1 2 3 4 4 8 9

一看，发现了一个很重要的规律，都有 0~ \cdots ~0 ~1 ~6 ~9。

所以猜测所有情况都可以由若干个 0 和 1~6~9 构成。

再试一试九位数，发现也是如此。

于是，改了改暴力程序，让程序输出符合条件的平方数，如下：

#include<bits/stdc++.h>
using namespace std;
multiset<int>s;
map<multiset<int>,int>mp;
int main()
{
    multiset<int>tmp;
    tmp.insert(0),tmp.insert(0),tmp.insert(0),tmp.insert(0),tmp.insert(0),tmp.insert(0),tmp.insert(1),tmp.insert(6),tmp.insert(9);//同样是九位数的程序，其他情况注意更改参数
    for(int i=1;i<=200000;++i)
    {
        long long k=1ll*i*i;
        if(k<100000000) continue;
        if(k>999999999) break;
        while(k) s.insert(k%10),k/=10;
        if(s==tmp) printf("%lld\n",1ll*i*i);
        s.clear();
    }
    return 0;
}

先试一试五位数的，发现程序给的是：

研究了一下，发现首先又 1690\cdots、1960\cdots 和 9610\cdots，这三个很显然，都是 169、196 和 961 乘以了 10^k，其中 k 为偶数，所以一定是平方数。

剩下的就是 10\cdots60\cdots90\cdots，也就是 169 的 1 与 6 之间和 6 与 9 之间插入相同数量的零，再在后面放若干个零构成的，首先因为插入的零是偶数，并且总数字个数是奇数，再加上有 169 三个数字，所以后面的零一定是偶数个，所以后面加的一定正确，只需要验证 10\cdots60\cdots9 是否一定正确即可，发现就是 10\cdots3 的平方，所以一定正确。

那么同理 961 的 1 与 6 之间和 6 与 9 之间插入相同数量的零，再在后面放若干个零构成的数也一定是平方数，也是正确的。

使用暴力程序在七位数和九位数验证，发现是正确的。

再计算一下我们发现了多少个平方数了，在其中插入的零可以是 [0,\frac{n-1}2-1] 个，一共有 \frac{n-1}2 个，169 和 961都可以，一共有 n-1 个，再加上 1960\cdots 的一个，刚好 n 个。

其实发现还有形如 61009 之类的数也满足条件，但是我们已经不需要了。

根据上面发现的构造方案可以很轻松的写出程序。

AC code

#include<bits/stdc++.h>
using namespace std;
long long T,n,a,sum,num;
int main()
{
    scanf("%lld",&T);
    while(T--)
    {
        scanf("%lld",&n);
        if(n==1){puts("1");continue;}//注意特判n=1
        printf("169");
        for(int i=4;i<=n;++i) printf("0");
        puts("");
        printf("961");
        for(int i=4;i<=n;++i) printf("0");
        puts("");
        printf("196");
        for(int i=4;i<=n;++i) printf("0");
        puts("");
        for(int i=1;i<n/2;++i)
        {
            printf("1");
            for(int j=1;j<=i;++j) printf("0");
            printf("6");
            for(int j=1;j<=i;++j) printf("0");
            printf("9");
            for(int j=3+2*i;j<n;++j) printf("0");
            puts("");
            printf("9");
            for(int j=1;j<=i;++j) printf("0");
            printf("6");
            for(int j=1;j<=i;++j) printf("0");
            printf("1");
            for(int j=3+2*i;j<n;++j) printf("0");
            puts("");
        }
    }
    return 0;
}