这道题我用和题解不太一样的方法推了一下式子，发现：

$\sum_{i=1}^A\sum_{j=1}^B[\operatorname{gcd}(i,j)=d]$ $=\sum_{i=1}^{A/d}\sum_{j=1}^{B/d}[\operatorname{gcd}(i,j)=1]$ $=\sum_{i=1}^{A/d}{[(B/id)\varphi(i)+\sum_{j=1}^{i\%j}[gcd(i,j)=1]]}$ 令 $f(i,j)=(j/i)\varphi(i)+f(j,i\%j)$，则原式等于

$\sum_{i=1}^{A/d}f(i,B/d)$

用类似gcd的形式求解即可。但样例过了，交上去成功爆零。请问是我思路有问题还是代码有问题？

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a,b,d;
bool flag[1000010];
ll phi[1000010];
int prime[1000010],cnt;
ll ans;
ll gcd(ll a,ll b){
    if(b==0)return 0;
    return b/a*phi[a]+gcd(b,a%b);
}
int main(){
    phi[1]=1;
    for(int i=2;i<=1000000;i++){
        if(!flag[i]){
            phi[i]=i-1;
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt;j++){
            if(i*prime[j]>1000000)break;
            flag[i*prime[j]]=true;
            if(i%prime[j]!=0)phi[i*prime[j]]=phi[i]*phi[prime[j]];
            else phi[i*prime[j]]=phi[i]*prime[j];
            if(i%prime[j]==0)break;
        }
    }
    cin>>a>>b>>d;
    for(int i=1;i<=a/d;i++){
        cout<<gcd(i,b/d)<<endl;
        ans+=gcd(i,b/d);
    }
    cout<<ans;
}