题解：AT_abc433_d [ABC433D] 183183

· · 题解

AT_abc433_D

赛时唐成啥了，没开 ll 吃了一发罚时，遗憾 1000pts 落败。。。

思路

观察题目，先让我们转化成数学：

a+b \times 10^{\operatorname{len}(b)} \equiv 0 \pmod{m}

（注：len(b)是b的长度）\ 注意到直接枚举 a 和 b 是超时的，考虑优化。\ 注意到虽然直接枚举 a 和 b 是超时的，但是 len(b) 在这道题里最高只有 9（题目保证 a_{i} \leq 1e9）。所以我们转变思路，先枚举出 a，然后枚举 len(b) ，用上面的公式计算是否合法就行了。

#include<bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
inline int read()
{
    int x=0,t=1;
    char c=getchar();
    while(c<'0' || c>'9')
    {
        if(c=='-')
            t=-1;
        c=getchar();
    }
    while(c>='0' && c<='9')
    {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*t;
}
inline void write(ll x)
{
    if(x<0)
    {
        x=-x;
        putchar('-');
    }
    if(x>=10) write(x/10);
    putchar(x%10^48);
    return ;
}
inline void write_L(ll x)
{
    write(x);
    putchar('\n');
}
const int N=2e5+10;
const int M=20;
int len[N];
ll pow10[M];
int get_len(int x)
{
    int ans=0;
    while(x)
    {
        ans++;
        x/=10;
    }
    return ans;
}
int main ()
{
    int n=read(),m=read();
    vector<int> vec[M];
    for(int i=1;i<=n;i++)
    {
        int x=read();
        int t=get_len(x);
        len[i]=t;
        vec[t].push_back(x);
    }
    pow10[0]=1;
    for(int i=1;i<=10;i++)
        pow10[i]=pow10[i-1]*10ll%m;
    ll ans=0;
    for(int l=1;l<=10;l++)
    {
        ll mul=pow10[l]%m;
        for(int k=1;k<=10;k++)
        {
            unordered_map<long long,int> cnt;
            for(int i:vec[k])
            {
                ll r=i*1ll*mul%m;
                cnt[r]++;
            }
            for(int i:vec[l])
            {
                ll t=(-i%m+m)%m;
                if(cnt.count(t))
                    ans+=cnt[t];
            }
        }
    }
    write_L(ans);
    return 0;
}

注：打比赛的时候太糖了，把单 log 打成双 log 了