CF10C Digital Root

原题链接

• 题意：给出 (1 <= n <= 100000) 的大小的数，然后要求 (a imes b eq c) 并且 (d(d(a) imes d(b) ) = d(c)) ,d函数是数根的意思。
• 题解：确实不懂数根的知识。数根有些性质，即 (a imes b = c) 成立，那么 (d(d(a) imes d(b) ) = d(c)) 也一定成立，反之则并不一定。可以发现数根只取到0-9,所以我们可以记录下来从1-n所有数，他数根值为 (i) 的数量，记为 (cnt_i) 然后即可遍历0-9三层for循环找到所有满足 (d(d(a) imes d(b) ) = d(c)) 的方案数，然后就是要减掉 (a imes b eq c) 的方案就是答案，并且在1-n中求 (a imes b = c) 的方案数，就是 (sum_{i=1}^{n} left lfloor frac{n}{i} ight floor),所以就是用第一次的值减第二次的值即可。
• 代码：

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <stack>
#include <vector>

using namespace std;
typedef long long ll;
const int N = 19;
const double eps = 1e-8;
struct node {
    double x, y;
}a[N];
int dp[1 << N];

int s(int x) {
    int ret = 0;
    while (x) {
        ret += x % 10;
        x /= 10;
    }
    return ret;
}
int d(int x) {
    if (s(x) <= 9)return s(x);
    else return d(s(x));
}
int cnt[110];
void solve() {
    ll sub = 0;
    int n;cin >> n;
    for (int i = 1; i <= n; i++) {
        cnt[d(i)] ++;
        sub += n/i;
    }
    ll sum = 0;
    for (int i = 0; i <= 9; i ++) {
        for (int j = 0; j <= 9; j++) {
            for (int k = 0; k <= 9; k++) {
                if (d(i * j) == k) {
                    sum += (ll)cnt[i] * cnt[j] * cnt[k];     
                } 
            }
        }
    }
    cout << sum - sub << endl;
    
}
signed main() {
    int t = 1;//cin >> t;
    while (t--) solve();
    return 0;
}