题目链接：I-hx的数列_华中农业大学第十二届程序设计竞赛新生赛（同步赛） (nowcoder.com)

Problem

给出一个整数N（3≤N≤1e12）,请问，从1~N中有多少个三元组是上升的等比数列。

Analyse

分析样例不难发现，当$N = 10$时，有$(1, 2, 4), (2, 4, 8), (1, 3, 9), (4, 6, 9)$这\(4\)个三元组是上升的等比数列，其公比分别为$2, 2, 3, \frac{3}{2}$，公比可以是一个有理数，从而可以用一个分数$\frac{t}{b}$来表示，为了避免重复计数，我们需要保证$gcd(t, b) = 1$始终成立。 所以我们就可以得到这个三元组的表达式，设首项为\(a_1\)，则三元组表达为： $$(a_1, a_1 * \frac{t}{b}, a_1 * \frac{t}{b} * \frac{t}{b})$$ 为了使得第三项是整数，需要保证$b^2 | a_1$，即$b^2$可以整除$a_1$，实际上是要求$a_1 * t * t$可以被$b * b$整除，但是因为$t, b$互质，所以只需保证$a_1$可以被$b ^2$整除，所以$a_1 = k * b^2$，而这也保证了第二项是整数，接下来枚举$t$。 $$\sum\limits_{t=2}^{sqrt(N)}\lfloor \frac{N}{t^2} \rfloor \sum\limits_{b=1}^{t-1}[gcd(b, t)=1]$$

不难发现式子可以转化为：

$$\sum\limits_{t=2}^{sqrt(N)}\lfloor \frac{N}{t^2} \rfloor \phi(t)$$

用线性筛筛出欧拉函数即可。

Code

#include 
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
int mu[maxn], phi[maxn], prefix_phi[maxn], prefix_mu[maxn];
map mp_mu, mp_phi;

void init(int N = maxn - 1)//N = maxn - 1
{
    bitset vis;
    vector prim(N + 5);
    vis[0] = vis[1] = true;
    phi[1] = 1;
    int k = 0;//k是质数集大小
    for(int i = 2; i <= N; ++ i)
    {
        if(!vis[i])prim[++ k] = i, phi[i] = i - 1;
        //遍历质数集
        for(int j = 1; j <= k && prim[j] * i <= N; ++ j)
        {
            vis[i * prim[j]] = true;//标记为合数

            if(i % prim[j] == 0)
            {
                phi[i * prim[j]] = phi[i] * prim[j];
                break;//避免重复
            }
            else phi[i * prim[j]] = phi[i] * (prim[j] - 1);
        }
    }

}
signed main()
{
    int n;scanf("%lld", &n);
    init();
    int ans = 0;
    for(int t = 2;t * t <= n; ++ t)
    {
        ans += phi[t] * (n / (t * t));
    }
    printf("%lld\n", ans);
    return 0;
}

对于每一个\(t\)，我们只需保证第三项是\(\le N\)即可，所以只需保证$a_1 * \frac{t}{b}, a_1 * \frac{t}{b} * \frac{t}{b} = k * t^2 \le N$，所以$k \le \lfloor \frac{N}{t^2} \rfloor$。（注意$a_1$一定可以被\$b^2$整除，所以可以直接将分母的$b^2$约去）。对于每一个$t$，我们都可以算出\(k\)的取值范围，也就是合法的\(k\)的个数。

第二项显然是合法的，不再赘述。

接下来确定\(t\)的范围，为了保证$a_3 = k * t^2 \le N$，故有$t^2 \le N$，同时不难发现，为了使得序列是上升的，有$t>1$。

所以可以得到以下表达式：

$$\sum\limits_{t=2}^{sqrt(N)}\lfloor \frac{N}{t^2} \rfloor \sum\limits_{b=1}^{t-1}[gcd(b, t)=1]$$

不难发现式子可以转化为：

$$\sum\limits_{t=2}^{sqrt(N)}\lfloor \frac{N}{t^2} \rfloor \phi(t)$$

用线性筛筛出欧拉函数即可。

Code

#include 
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
int mu[maxn], phi[maxn], prefix_phi[maxn], prefix_mu[maxn];
map mp_mu, mp_phi;

void init(int N = maxn - 1)//N = maxn - 1
{
    bitset vis;
    vector prim(N + 5);
    vis[0] = vis[1] = true;
    phi[1] = 1;
    int k = 0;//k是质数集大小
    for(int i = 2; i <= N; ++ i)
    {
        if(!vis[i])prim[++ k] = i, phi[i] = i - 1;
        //遍历质数集
        for(int j = 1; j <= k && prim[j] * i <= N; ++ j)
        {
            vis[i * prim[j]] = true;//标记为合数

            if(i % prim[j] == 0)
            {
                phi[i * prim[j]] = phi[i] * prim[j];
                break;//避免重复
            }
            else phi[i * prim[j]] = phi[i] * (prim[j] - 1);
        }
    }

}
signed main()
{
    int n;scanf("%lld", &n);
    init();
    int ans = 0;
    for(int t = 2;t * t <= n; ++ t)
    {
        ans += phi[t] * (n / (t * t));
    }
    printf("%lld\n", ans);
    return 0;
}