题目链接

https://codeforces.com/problemset/problem/1213/C

解题思路

最初的思路：
枚举n/m的商，同时统计所枚举到的商与m的乘积对10取模得到的每种个位的数量；单独一个10次的循环，统计ans。
方法没错，但是时间不够，如果n很大而m很小，时间复杂度最高可以到1e16。
大佬的思路：
我们要找能整除m的数，那么这些数一定可以表示为x*m且x<=n/m
我们可以发现1*m%10=11*m%10=21*m%10=……=111*m%10=121*m%10=……，只要x的个位相等，那么这些x与乘以m之后的个位也相等。
小证明一下：一个数A由n位组成，从高位到低位的每一个数字为a[n-1],a[n-2],a[n-3],……,a[1],a[0]，
A的大小为a[n-1]*10^(n-1)+a[n-2]*10^(n-2)+……+a[1]*10^1+a[0]*10^0
由取模运算规则可得，

A%10 = 
( a[n-1]*10^(n-1)+a[n-2]*10^(n-2)+……+a[1]*10^1+a[0]*10^0 )%10 = 
( a[n-1]*10^(n-1) )%10 + ( a[n-2]*10^(n-2) )%10 + …… + ( a[1]*10^1 )%10 + ( a[0]*10^0 )%10 =
a[0]

证明完了。
想表达的就是，任意的x*m其中x<=n/m，只要x的个位相等，那么x*m的个位也相等。
这样一来我们就不用像最初思路那样，把所有的x都枚举一遍了。
我们只需要统计一下x=1~9时x*m的个位是什么就行了。
再统计一下x<=n/m的范围内，x的个位为1~9的数量，用数量乘以权重（即x=1~9范围内x*m的个位的值），求和，结束。

大佬题解

AC代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int T;
ll n,m,cnt[10],ans;
int main()
{
    cin>>T;
    while(T--)
    {
        ans=0;memset(cnt,0,sizeof cnt);

        cin>>n>>m;

        ll aa=n/m%10;
        ll bb=n/m/10;

        for(int i=1;i<=9 && i*m<=n;i++)//求权重，对应解题思路中x=1~9，x*m的个位；即cnt[x]=x*m%10
        cnt[i]=i*m%10;

        for(int i=1;i<=9;i++)
        ans+=cnt[i]*(i<=aa?bb+1:bb);//如果我们枚举的个位比最后n/m的个位大，那么数量就只有n/m/10个，否则会多一个；举个例子，假设n/m（即解题思路中x<=n/m的x的最大值）为21，则个位为1的为1，11，21，但是个位为2的只有2，12，同样，个位为3的只有3，13

        cout<<ans<<endl;

    }
}

总结

凡是沾点数论知识的都不会，看题解也得看半年！！wsfw