#10 C. Digital Root （数论）

灰太狼 2022-06-17 14:42 121阅读 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 条评论，121人围观）

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

相关阅读

相关 Ubuntu 13.10使用root登陆

使用root用户的人都应该知道，root用户对整个系统拥有这全部的权限！ Ubuntu默认是禁用了root用户的登陆使用root用户登陆Ubuntu需要一下步骤 1、首

偏执的太偏执、/ 2022年09月19日 04:23/ 0 赞/ 107 阅读

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

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

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

相关 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 赞/ 142 阅读

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

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

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

相关 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 赞/ 156 阅读

相关【数论】c

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

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

相关 codeforces 915C. Permute Digits

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

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

相关 Educational Codeforces Round 59 [Rated for Div. 2] B. Digital root

Today at the lesson of mathematics, Petya learns about the digital root. The digital ro

r囧r小猫/ 2022年03月22日 07:49/ 0 赞/ 149 阅读

相关 UVALive2247 Prime Digital Roots

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

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

相关 Revolving Digits

算法：扩展KMP + KMP找循环节 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] inclu

港控/mmm°/ 2021年10月23日 11:56/ 0 赞/ 199 阅读