自动搬运

查看原文

来自洛谷，原作者为

	jsisonx Jsisnxn

搬运于2025-08-24 23:13:48，当前版本为作者最后更新于2025-08-19 22:25:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题目分析

不难想到，可以分别对每一个 $a_i$ 计算有多少个满足条件的 $d$，记为 $P_i$，则答案等于 $\sum\limits_{i=1}^{n} P_i$。

下面考虑如何求 $P_i$。由于 $a_i\mid i\times d$，则 $\frac{a_i}{(a_i,i)}\mid \frac{i}{(a_i,i)}\times d$。而又因为 $(\frac{a_i}{(a_i,i)},\frac{i}{(a_i,i)})=1$，所以 $\frac{a_i}{(a_i,i)} \mid d$。

由此，问题就变成了小于等于 $n$ 的数中有多少是 $\frac{a_i}{(a_i,i)}$ 的倍数，显然 $P_i=\lfloor \frac{n\times (a_i,i)}{a_i} \rfloor$。

代码

#include<bits/stdc++.h>
#define N 200001
using namespace std;
int gcd(int a,int b){
    if(b==0){
        return a;
    }
    return gcd(b,a%b);
}
int a[N];
long long ans=0;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        int g=gcd(a[i],i);
        a[i]/=g;
        ans+=(long long)n/(long long)a[i];
    }
    cout<<ans;
    return 0;
}