#10 C. Digital Root （数论）

灰太狼 2022-06-17 14:42 186阅读 0赞

题目链接：  
[点击打开链接][Link 1]  
[http://codeforces.com/contest/10/problem/C][Link 1]  
题意：  
定义d(x)为x的数字根，找出n以内的满足d(z)=d(d(x)⋅d(y))但不满足x⋅y=z这样的x,y,z有多少组?  
d(A)是数根，其实就是A%9.  
题解：  
容斥原理，首先把所有的d(A)d(B)=d(C)的都计算了。  
然后减去AB==C且d(A)d(B)=d(C)的，由于显然AB=C，那么d(A)d(B)=d(C).  
所以我们只需要减去AB=C的情况就好了。

首先我们能够知道d(x⋅y)=d(d(x)⋅d(y)),那么我们只要找出n以内的数的约数的个数，即n/i就知道了满足条件的情况数,作为ans1。  
然后我们通过记录数字根分别是1−9的数的个数，然后直接利用  
a\[i\]∗a\[j\]∗a\[k\]，其中，(k=i⋅j)  
即a\[i\]∗a\[j\]∗a\[i∗jmod9\]  
可以计算得到k分为因数i和j的所有情况，作为ans2。  
然后用ans2−ans1即可。

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll a[12];
    int main()
    {
        int n;
        ll ans=0;
        ll ans1=0,ans2=0;
        cin>>n;
        for(int i=1;i<=n;i++){
            a[i%9]++;
            ans1 += n/i;
        }
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                ans2 +=a[i]*a[j]*a[i*j%9];
            }
        }
        ans=ans2-ans1;
        cout<<ans<<endl;
        return 0;
    }

[Link 1]: http://codeforces.com/contest/10/problem/C

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU-1163 Eddy's digital Roots

前置芝士: 同余定理，快速幂这个题目是杭电上的一道数论相关的题目如果暴力的话是一定会超时的，这个时候我们就要用到同余定理来优化。同余定理是数论中的重要概念，下面贴

末蓝、/ 2023年06月30日 01:43/ 0 赞/ 30 阅读

相关 Digits

\\(Digits\\) ![m6C1AO.png][] 这道题目比较简单，首先先打出来暴力，然后一看\\(b\\)的范围，瞬间想到快速幂。快速幂的精髓是什么？

偏执的太偏执、/ 2023年06月01日 15:00/ 0 赞/ 71 阅读

相关 C. Strange Function (思维+数论)

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZCN5a2X5LiN6

墨蓝/ 2022年09月13日 06:19/ 0 赞/ 237 阅读

相关 Digital Roots

Digital Roots Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述 The digi

短命女/ 2022年08月10日 04:44/ 0 赞/ 54 阅读

相关 leetcode-258.add digits/Digital root

leetcode-258.Add Digits Given a non-negative integer num, repeatedly add all its digi

痛定思痛。/ 2022年07月28日 00:13/ 0 赞/ 231 阅读

相关 #10 C. Digital Root （数论）

题目链接： [点击打开链接][Link 1] [http://codeforces.com/contest/10/problem/C][Link 1] 题意：

灰太狼/ 2022年06月17日 14:42/ 0 赞/ 187 阅读

相关 Digital Roots 求一个数的数字根

The digital root of a positive integer is found by summing the digits of the integer.

Dear 丶/ 2022年06月08日 00:59/ 0 赞/ 239 阅读

相关【数论】c

c 【题目描述】给定一个正整数n，在\[1,n\]的范围内，求出有多少个无序数对(a,b)满足gcd(a,b)=a xor b。【输入格式】输入共一行，一

男娘i/ 2022年06月06日 04:44/ 0 赞/ 290 阅读

相关 codeforces 915C. Permute Digits

题目链接：[http://codeforces.com/problemset/problem/915/C][http_codeforces.com_problemset_pro

矫情吗；*/ 2022年05月09日 16:42/ 0 赞/ 234 阅读

相关 UVALive2247 Prime Digital Roots

Regionals 2001 >> South Pacific 问题链接：[UVALive2247 Prime Digital Roots][]。基础训练题，用C语

Myth丶恋晨/ 2022年01月09日 10:53/ 0 赞/ 119 阅读