CF10C Digital Root

链接

Idea

看完题有以下结论

[xequiv s(x)\%9 ]

接着我们来算(d(x))的值，知道(d(x))的值域是([1,9],d(x)in mathbb Z)

那么很容易算出

[d(x)=egin{cases}x\%9quad(x\%9 ot=0)\9 (x\%9=0)end{cases} ]

(xin [1,9])，显然......

假设对于(y<x)的(y)均成立

若(s(x))不是(9)的倍数

那么(d(x)=d(s(x))=s(x) ext{mod} 9=x ext{mod} 9)

否则，(d(x)=9);

统计([1,n])有多少个数满足(d(x)=1,2,3,...,9)

暴力枚举([1,9])就好了

最后会多出(a imes b=c)的答案，减掉就好了

个数就是(a imes b)的解数(ans1)

如果(A)固定，则(ans1=leftlfloorfrac{n}{A} ight floor)

那么最终的(ans1=sum_{i=1}^{n}leftlfloorfrac{n}{i} ight floor)

上面这个东西就是除法分块,最后因为(n)有点大，要开(long;long)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<string>
#define int long long
#define maxn 200001 
#define inf 2147483647
#define mod 10003
#define eps 1e-6
#define pi acos(-1.0)
#define de(x) ((x)*(x))
using namespace std; 
inline int read(){
    int x=0,f=1; char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)) {x=x*10+ch-48;ch=getchar();}
    return x*f;
}
inline void put(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) put(x/10) ;
	putchar(x%10+48);
}
inline int d(int x){return (x%9)?(x%9):9;}
int cnt[10],n,ans;
signed main(){
	n=read();
	for(int i=1;i<=n;i++) cnt[d(i)]++;
	for(int i=1;i<=9;i++)
	for(int j=1;j<=9;j++)
	for(int k=1;k<=9;k++)
	if(i*j%9==k%9) ans+=cnt[i]*cnt[j]*cnt[k];
	for(int l=1,r;l<=n;l=r+1){
		r=min(n,n/(n/l));
		ans-=(n/l)*(r-l+1);
	}
	printf("%lld",ans);
    return 0;
}