洛谷题目传送门

分数其实就是一个幌子，实际上就是求互质数对的个数（除开一个特例\((1,1)\)）。因为保证了\(a<b\)，所以我们把要求的东西拆开看，不就是\(\sum_{i=2}^n\phi(i)\)吗？

关于通过筛素数线性求欧拉函数的一点思路总结在蒟蒻的blog里

剩下的就是记一个前缀和了。

#include<cstdio>

#define R register

const int N=1000001;

int pr[N],phi[N];

long long ans[N];

bool f[N];

int main(){

    R int n,i,j,k,p=0;

    for(i=2;i<N;++i){

        if(!f[i])phi[pr[++p]=i]=i-1;

        ans[i]=ans[i-1]+phi[i];

        for(j=1;j<=p&&(k=i*pr[j])<N;++j){

            f[k]=1;

            if(i%pr[j])

                phi[k]=phi[i]*(pr[j]-1);

            else{

                phi[k]=phi[i]*pr[j];

                break;

            }

        }

    }

    while(scanf("%d",&n),n)

        printf("%lld\n",ans[n]);

    return 0;

}