Codeforces 10C Digital Root

题目大意：定义$d(x)$为$x$的“数字根”，给定$N$，求三元组$(A, B, C)(A, B, C\in [1, N])$的个数，其中$d(d(A)d(B))=d(C)$且$AB\neq C$。

题解

可以发现$d(xy)=d(d(x)y)=d(d(x)d(y))$。所以可以先求出所有不包含条件$AB\neq C$的三元组的数目$N_1$，然后减掉包含该条件的三元组的数目$N_2$。

$N_2$容易求出，等同于$1, \cdots, N$每一个数的约数的数目之和，即$N_2=\sum_{i=1}^{N} \lfloor \frac{N}{i} \rfloor$。

$N_1$也容易求，由$d(xy)=d(d(x)d(y))$可知对于不同的$A, B$，$d(AB)$具有周期性。故可以先求出$N=9$的情况，然后根据周期性算出$N_1$。（这里可以想象一个$N\times N$的棋盘上相邻的$9\times 9$宫格之间情况是相同的）
答案就是$N_1-N_2$。

#include <bits/stdc++.h>
using namespace std;
int n, ss[10][10][10] = {0};
long long ans = 0, cnt[10] = {0};
int dr(int x){
    return (x % 9 ? x % 9: 9);
}
int main(){
    cin >> n;
    for(int i = 1; i <= 9; ++i){
        for(int j = 1; j <= 9; ++j){
            ss[i][j][dr(i * j)]++;
            for(int k = 1; k <= 9; ++k)
                ss[i][j][k] += ss[i][j - 1][k];
        }
    }
    for(int i = 1; i <= 9; ++i)
        for(int j = 1; j <= 9; ++j)
            for(int k = 1; k <= 9; ++k)
                ss[i][j][k] += ss[i - 1][j][k];
    long long res = 0;
    for(int i = 1; i <= n; ++i){
        res += 1ll * (n / i);
    }
    int kk = n / 9, r = n % 9;
    for(int i = 1; i <= 9; ++i)
        cnt[i] += 1ll * kk * kk * ss[9][9][i], 
        cnt[i] += 2ll * kk * ss[r][9][i], 
        cnt[i] += 1ll * ss[r][r][i];
    for(int i = 1; i <= 9; ++i)
        ans += ((n + 9 - i) / 9) * cnt[i];
    cout << ans - res << endl;
    return 0;
}