题目大意:定义$d(x)$为$x$的“数字根”,给定$N$,求三元组$(A, B, C)(A, B, Cin [1, N])$的个数,其中$d(d(A)d(B))=d(C)$且$ABneq C$。
题解
可以发现$d(xy)=d(d(x)y)=d(d(x)d(y))$。所以可以先求出所有不包含条件$ABneq C$的三元组的数目,然后减掉包含该条件的三元组的数目。
容易求出,等同于$1, cdots, N$每一个数的约数的数目之和,即。
也容易求,由$d(xy)=d(d(x)d(y))$可知对于不同的$A, B$,$d(AB)$具有周期性。故可以先求出$N=9$的情况,然后根据周期性算出。(这里可以想象一个$Ntimes N$的棋盘上相邻的$9times 9$宫格之间情况是相同的)
答案就是。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
|
using namespace std; int n, ss[10][10][10] = {0}; long long ans = 0, cnt[10] = {0}; int (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; }
|
近期评论