Bài C - Codeforces Beta Round #10

Bài C:
Đề bài: Cách đây không lâu, Billy bắt gặp một vấn đề, đó là: cho ba số tự nhiên A,B và C thuộc dãy [1..N], và chúng ta phải kiểm tra liệu rằng phương trình AB=C có đúng hay không?. Gần đây, Billy đã học về khái niệm digital root của 1 số. Chúng tôi nên nhắc lại rằng digital root d(x) của một số x là tổng s(x) của tất cả các chữ số, nếu s(x)<=9, ngược lại nó là d(s(x)). Ví một, digital root của số 6543 được tính như sau: d(6543)=d(6+5+4+3)=d(18)=d(9). Billy phải điểm rằng digital root của một tích các số có bằng digital root của tích các digital root các số, nghĩa là d(xy)=d(d(x).d(y)). Và lời giải dưới đây có ảnh hưởng đến tâm trí của anh ấy: để tính digital root và kiểm tra rằng điều kiện này đã đáp ứng chưa. Tuy nhiên, Billy nghi ngờ rằng điều kiện này đã đủ chưa. Và đó là lý do anh ta hỏi bạn để tìm ra nhiều ví dụ cho vấn đề được cho này thỏa mãn thuật toán được đề nghị bởi Billy có lỗi.
Đầu vào:
+ Dòng đầu tiên chứa 1 số duy nhất N (1<=N<=10^6).
Đầu ra:
+ In ra 1 số - số lượng các số A,B và C được yêu cầu từ dãy [1..N]
Ví dụ:
Đầu vào:
4
Đầu ra:
2
/**/
Đầu vào:
5
Đầu ra:
6
Chú thích
Ở ví dụ đầu tiên ta có bộ ba (3,4,3) và (4,3,3)
Lời giải:

#include<iostream>
int n,i,j;
__int64 t,a[9];
int main()
{
 std::cin>>n;
 for(i=1;i<=n;i++)a[i%9]++,t-=n/i;
 for(i=0;i<9;i++)for(j=0;j<9;j++)t+=a[i]*a[j]*a[i*j%9];
 std::cout<<t;
}