题目翻译
你决定在考试的一道题中打表。该题要求你计算的是一个二元函数 \(f(x,y)\)，定义域为 \(x,y \in [1,+\infty]\ \ x,y \in \mathbb{Z}^{+}\)。
该函数有一个性质，就是如果你知道了 \(f(x,y)\)，就可以很方便的计算出 \(f(xk,yk)(k \in \mathbb{Z^{+}},k > 1)\)，因此，你的表中不需要包含这些值。
多组数据，每组数据给出一个整数 \(N\)，你需要求出如果需要打出 \(x,y \in [1,N]\) 的表，需要至少多少个 \(f\) 函数的值。若 \(N = 0\)，则结束程序。
\(0 \leq N \leq 5 \times 10^{4}\)。
简要题意
多组数据，每组数据给出一个整数 \(N\)，你需要求出位于区间 \([1,N]\) 的两个正整数所组成的所有有序二元组中，两数互质的二元组个数。若 \(N = 0\)，则结束程序。
\(0 \leq N \leq 5 \times 10^{4}\)。
思路
首先通过贪心思想将原题目转换为【简要题意】中的题目。然后考虑计数。
显然，除了 \((1,1)\) 之外，其他的互质二元组 \((x,y)\) 都满足 \(x\neq y\)。
于是我们将有序二元组转换为无序二元组，且钦定 \(y<x\)，不难发现，答案就是：
\[\sum_{i=1}^{N}{\varphi(i)} \]答案就是上式的两倍，然后减去多算了一次的 \((1,1)\)。答案就是：
\[2\cdot (\sum_{i=1}^{N}{\varphi(i)})-1 \]然后使用线性筛筛出 \(N\) 范围内的 \(\varphi(i)\)，预处理前缀和，就可以直接 \(O(1)\) 回答询问了。
时间复杂度 \(O(T+N)\)，\(T\) 为数据组数。
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int phi[10000005],prime[10000005],tot;
bool vis[10000005];
void sieve(){
vis[1]=1,phi[1]=1;
for(int i=2;i<=500000;i++){
if(!vis[i]){
prime[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&i*j<=500000;j++){
vis[i*prime[j]]=1;
if(i%prime[j]){
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
else{
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
}
}
for(int i=1;i<=500000;i++){
phi[i]=phi[i-1]+phi[i];
}
}
signed main(){
sieve();
while(1){
int n;
cin>>n;
if(n==0)break;
cout<<(2*phi[n]-1)<<'\n';
}
return 0;
}