UVA 10820 Send a Table

https://vjudge.net/problem/UVA-10820

題意：

有一張表 f[x][y]，共x*y個數

現在要删去所有的 f[x*k][y*k] ,k>1

最後還剩多少個數

題意轉化：有多少個二進制組（x，y）滿足 gcd（x，y）=1

若x<y，則 f[][y]=phi(y)

是以 ans= （2* Σ phi（y））+1   y∈[2,n]

加的1為（1,1）

線性篩出歐拉函數求和即可

作者：xxy

本文版權歸作者所有，轉載請用連結，請勿原文轉載，Thanks♪(･ω･)ﾉ。