首页 > 代码库 > Codeforces 10C Digital Root 规律题

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

*/