Codeforces 10C Digital Root

知识点：计数原理、数学推理、反向思考

题目

Not long ago Billy came across such a problem, where there were given three natural numbers A, B and C from the range [1, N], and it was asked to check whether the equation AB = C is correct. Recently Billy studied the concept of a digital root of a number. We should remind you that a digital root d(x) of the number x is the sum s(x) of all the digits of this number, if s(x) ≤ 9, otherwise it is d(s(x)). For example, a digital root of the number 6543 is calculated as follows: d(6543) = d(6 + 5 + 4 + 3) = d(18) = 9. Billy has counted that the digital root of a product of numbers is equal to the digital root of the product of the factors’ digital roots, i.e. d(xy) = d(d(x)d(y)). And the following solution to the problem came to his mind: to calculate the digital roots and check if this condition is met. However, Billy has doubts that this condition is sufficient. That’s why he asks you to find out the amount of test examples for the given problem such that the algorithm proposed by Billy makes mistakes.

输入

The first line contains the only number N (1 ≤ N ≤ 106).

输出

Output one number — the amount of required A, B and C from the range [1, N].

样例

输入1

4

输出1

2

输入2

5

输出2

6

提示

For the first sample the required triples are (3, 4, 3) and (4, 3, 3).

题意

Digital Root的递归定义为：若一个数字的各位数字之和小于等于9则为各位数字之和，否则为各位数字之和的Digital Root，记为d(x)，且有d(xy)=d(d(x)d(y))，即乘积的Digital Root等于Digital Root的乘积的Digital Root。有人认为只要d©=d(d(A)d(B))就可以判断C=AB，其中A，B，C均为正整数且不超过N。存在A，B，C的不同组合，使得这个组合能反驳这个观点，要求输出组合数量。

思路

1. Digital Root通俗的理解为，只要一个数字的位数大于1位就将各位数字相加得到新的数，重复操作得到的1位数就是Digital Root。
2. 反驳观点的方法为，找到一对A，B，C使得AB≠C，但d（C）=d(d(A)d(B))。
3. 正向考虑，发现AB≠C的组合太多，若使用三重循环分别枚举A，B，C，然后求d(A),d(B),d（C）判断d（C）=d(d(A)d(B))，时间复杂度为O(n^3)，会超时。
4. 反向考虑，所有能反驳观点的组合中，必满足d（C）=d(d(A)d(B))，但AB≠C。而根据通俗理解可以知道等号左右取值范围只能是0~9，但对0~9中任意一个数字（设为e）而言，等号左右等于e的组合有很多，根据分步计数原理，为满足d（C）=e的C的个数乘以满足d(d(A)d(B))=e的A的个数乘满足d(d(A)d(B))=e的B的个数，分类计数原理得总数为e取0~9时满足上述条件的A，B，C组合个数的和。再从得到的和中减去满足AB=C的组合。
5. 分析满足d（C）=d(d(A)d(B))的组合个数。考虑到A，B，C都小于N，可以枚举1~N的所有值，并计算值的Digital Root，就可以统计Digital Root为0~9的数字分别为有多少，从而在后面的处理使用O（1）得到d(x)=e时x的取值个数，x取A，B，C即可得到A，B，C的取值个数。
6. 通过d（C）=e计算C的个数可直接用上述方法。为了通过d(d(A)d(B))=e计算A，B的组合个数，可枚举d(A)，d(B)（属于0~9），如果d(d(A)d(B))=e则把d(A)，d(B)的A，B的取值个数相乘再乘以之前算出的d（C）的C的个数。当然因为d(d(A)d(B))算出的值可用作得到d（C）的个数，故可以直接把d(A)，d(B)，d(d(A)d(B))的A，B，C的取值个数相乘。
7. 分析AB=C的组合个数。AB=C<=N，所以B<=N/A，即B取值为1~N/A，可枚举A从1~N，N/A为B的取值个数，而C可由A，B计算得到，A，B确定时，C的取值只有一个，所以组合个数为A从1~N时B的取值个数的和。
8. 分析d(x)的计算方法，可直接使用定义计算，另一种计算方法需要证明：
   当x%9==0时，d(x)=9;
   当x%9!=0时，d(x)=x%9.
   证明如下：
   x==9时，d(x)=9
   x<9时，d(x)=x%9
   x>9时，
   设x=x0+x1*10+x2*100+…+xn*1000…
   =x0+x1+x2+…+xn+x1*9+x2*99+…+xn*999…
   =d(x)+9*(x1*1+x2*11+…+xn*111…)
   d(x)=x%9
   证毕。
   （数论杀我）
   实现思路见代码。

代码

//克服WA难，终得AC
#include"bits/stdc++.h"
#define ll long long
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define reb(i,a,b) for(ll i=a;i<=b;i++)
#define rev(i,a,b) for(ll i=a-1;i>=b;i--)
#define red(i,a,b) for(ll i=a;i>=b;i--)
#define clr(arr,val) memset(arr,val,sizeof arr)
using namespace std;

ll cnt[20];//1~N中d(x)=i的个数

ll d(ll x) {
   
  return x%9?x%9:9;
}

int main() {
   
  ll n;
  cin>>n;
  //枚举1~N，对d(i)出现次数计数
  reb(i,1,n) cnt[d(i)]++;
  ll ans=0;
  //计算d(C)=d(d(A)d(B))的个数。枚举d(A)、d(B)，cnt[i]为A的个数，cnt[j]为B的个数，cnt[d(i*j)]为通过d(A)和d(B)计算出的C的个数。
  reb(i,0,9) reb(j,0,9) ans+=cnt[i]*cnt[j]*cnt[d(i*j)];
  //计算AB=C的个数。枚举A，计算B的个数，从答案中减去
  reb(i,1,n) ans-=n/i;
  cout<<ans<<endl;
  return 0;
}