#10 C. Digital Root （数论）

#10 C. Digital Root （数论）

首先我们能够知道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代码：

#includeusing 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<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。