题解：P12221 [蓝桥杯 2023 国 Java B] 序列

jsisonx · 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;
}