CF10C题解

ncwzdlsd · 2023-01-07 10:15:06 · 题解

显然可知，d(x)=x\bmod9，所以 d(d(a)\cdot d(b))=(a\times b)\bmod9=c\bmod9。

由于 a\times b\neq c，所以考虑容斥原理，即用 (a\times b)\bmod9=c\bmod9 的方案数减去 a\times b=c 的方案数。

首先我们可以用两重循环解决 [1,n] 中余数为 [0,8] 的个数从而得出前面这坨方案数；对于后面这坨，相当于对每个 c 求 c 的因数，由于 a、c 确定，所以 b 也确定，所以我们只要求 \sum_{i=1}^n\lfloor\dfrac{n}{i}\rfloor 即可。

代码实现也比较简单，看了一下我的代码好像是目前题解里最短的诶QwQ

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,ans,d[10];
signed main()
{
    cin>>n;
    for(int i=1;i<=n;++i) ans-=n/i,++d[i%9];
    for(int i=0;i<9;++i)
        for(int j=0;j<9;++j)
            ans+=d[i]*d[j]*d[i*j%9];
    cout<<ans;
    return 0;
}