ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 正文

hx的数列(数论)

2022年12月4日 107点热度 0人点赞 0条评论

题目链接: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\)。

对于每一个\(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 <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
int mu[maxn], phi[maxn], prefix_phi[maxn], prefix_mu[maxn];
map<int, int> mp_mu, mp_phi;

void init(int N = maxn - 1)//N = maxn - 1
{
    bitset<maxn> vis;
    vector<int> 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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ gcd 互质 思维 数论 欧拉函数 算法竞赛 线性筛法
最后更新:2023年1月20日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • Problem
  • Analyse
  • Code

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号