首页 > 资讯 > 其他 > 正文

C.Digital Root（数论）求解

17-12-23 来源：[db:作者]

收藏我要投稿

Description

定义函数d(x)为x的数字根，即若x≤9，则d(x)=x；否则d(x)=d(s(x))，其中s(x)为x的各位数之和

问存在多少三元组(A,B,C)满足A,B,C∈[1,N]，d(C)=d(d(A)d(B))但C≠AB

Input

一个整数N(1≤N≤106)

Output

输出满足条件的三元组(A,B,C)数量

Sample Input

Sample Output

Solution

首先，d(x)=(x?1)%9+1，由此可以求出[1,N]中满足d(x)=i的x数量num[i]

然后，求出所有满足d(C)=d(d(A)d(B))的三元组数量，只需枚举d(A)=i,d(B)=j，那么对答案的贡献就是num[i]?num[j]?num[d(i?j)]

最后，求出不合法三元组从答案中减去，即满足C=AB的三元组，这个数量就等于[1,N]中每个数的因子数，进而，考虑[1,N]中以i为因子的数有?ni?个，累加即可

Code

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pairP;
const int INF=0x3f3f3f3f,maxn=100001;
int d(int x)
{
    return (x-1)%9+1;
}
int num(int n,int x)
{
    return n/9+(n%9>=x?1:0);
}
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        ll ans=0;
        for(int i=1;i<=9;i++)
            for(int j=1;j<=9;j++)
                ans+=1ll*num(n,i)*num(n,j)*num(n,d(i*j));
        for(int i=1;i<=n;i++)ans-=n/i;
        printf("%I64d\n",ans);
    }
    return 0;
}

点击复制链接与好友分享!回本站首页