Codeforces 10C Digital Root 法冠军

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<set>

#include<vector>

#include<map>

#include<math.h>

#include<string>

#include<stdlib.h>

#include<algorithm>

using namespace std;

#define N 1000005

#define ll __int64

ll num[10],n;

ll go(ll x){

	ll ans = x;

	while(ans>=10){

		ans = 0;

		while(x) {

			ans += x%10;

			x /= 10;

		}

		x = ans;

	}

	return ans;

}

int main(){

	ll i,j,k;

	while(~scanf("%I64d",&n))

	{

		memset(num, 0, sizeof num);

		ll ans = 0;

		for(i=1;i<=n;i++)	num[go(i)]++, ans -= n/i;

		for(j=0;j<10;j++)

			for(k=0;k<10;k++)

				ans+=num[k]*num[j]*num[go(k*j)];

		printf("%I64d\n",ans);

	}

	return 0;

}

/*

2

1 2

3

1 2 3

*/