题解 CF10C 【Digital Root】

2018-08-12 19:52:40


按理说已经A了,但是你谷现在的RemoteJudge有毒,所以Luogu上显示UKE。。。

没错那一片Unaccepted都是我

首先要知道一个叫做数字根的东西,就是题目里说 $d()$ 。

其实, $$d(x)=\begin{cases}x\%9,\quad x\%9\neq0\\9,\qquad\ \ x\%9=0 \end{cases} $$

我们把 $9$ 看做 $0$ ,那么

$$d(x)=x\%9$$

那么先处理出 $d(a)\cdot d(b)=d(c)$ 的部分,然后处理出 $a\cdot b=c$ 的部分,两者相减即为答案。

后一部分很容易求出,即1~n的约数个数和,记为 $ans2$ 。

考虑每一个数的贡献,即:

$$ans2=\sum_{i=1}^{n}\left\lfloor\frac{n}{i}\right\rfloor$$

前一部分也不难。在求 $ans2$ 时,顺便求出一个数组 $a[]$ , $a[i]$ 表示 $[1,n]$ 内有多少个数的 $d()$ 为 $i$ 。

那么枚举 $d(a)$ 和 $d(b)$ ,求出 $d(c)$ ,再计数。

记第二部分的答案为 $ans1$ ,则:

$$ans1=\sum_{i=0,j=0}^{8}a[i]\times a[j]\times a[(i\times j)\%9]$$

最终的答案为 $ans1-ans2$ 。

(然而我的程序里 $ans1$ 和 $ans2$ 是反过来的)

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int a[10];

mainint main() {
    int n=read();
    int ans1=0,ans2=0;
    for (re int i=1;i<=n;i++) a[i%9]++,ans1+=n/i;
    for (re int i=0;i<9;i++)
        for (re int j=0;j<9;j++)
            ans2+=a[i]*a[j]*a[(i*j)%9];
    printf("%I64d\n",ans2-ans1);
    return 0;
}