LGP5495 Dirichlet 前缀和

朱雀 2023-10-11 11:16 29阅读 0赞

[题目][Link 1]

不是很明白为什么要叫做模板

考虑到\\(a\_i\\)能对\\(b\_j\\)产生贡献，当且仅当\\(a\_i=\\prod p\_k^\{a\_k\},b\_j=\\prod p\_k^\{b\_k\},\\forall k \\ a\_k\\leq b\_k\\)，于是我们把每一个质数次幂看成一维，相当于对\\(a\\)数组求一个高维前缀和

于是我们枚举每一个质数次幂，利用高维前缀和的方式来做就行了，复杂度同埃筛\\(\\operatorname\{O(n\\ log\\ log\\ n)\}\\)

#include<bits/stdc++.h>
    #define re register
    #define uint unsigned int
    const int maxn=2e7+5;
    uint seed,a[maxn],ans;
    int n,f[maxn],p[maxn>>2];
    inline uint getnxt(){
        seed^=seed<<13;seed^=seed>>17;
        seed^=seed<<5;return seed;
    }
    int main() {
        scanf("%d%u",&n,&seed);
        for(re int i=2;i<=n;i++) {
            if(!f[i]) p[++p[0]]=i;
            for(re int j=1;j<=p[0]&&p[j]*i<=n;j++) {
                f[p[j]*i]=1;
                if(i%p[j]==0) break;
            }
        }
        for(re int i=1;i<=n;i++) a[i]=getnxt();
        for(re int i=1;i<=p[0];i++)
            for(re int j=2;j*p[i]<=n;j++)
                a[p[i]*j]+=a[j];
        for(re int i=2;i<=n;i++) a[i]+=a[1],ans^=a[i];
        printf("%u",ans^a[1]);
        return 0;
    }

转载于:https://www.cnblogs.com/asuldb/p/11355745.html

[Link 1]: https://www.luogu.org/problem/P5495

发表评论取消回复

表情：

评论列表（有 0 条评论，29人围观）

还没有评论，来说两句吧...

相关阅读

相关 795. 前缀和

输入一个长度为 n 的整数序列。接下来再输入 m 个询问，每个询问输入一对 l,r。对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。输入格式第一行包含两个整数...

古城微笑少年丶/ 2024年05月01日 16:07/ 0 赞/ 72 阅读

相关前缀和讲解

前缀和输入一个长度为 n 的整数序列。接下来再输入 m 个询问，每个询问输入一对 l,r。对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。输入格

深藏阁楼爱情的钟/ 2024年03月31日 14:28/ 0 赞/ 79 阅读

相关前缀和模板

class Solution { public void func(int[] nums) { int n = nums.len

逃离我推掉我的手/ 2024年03月25日 10:02/ 0 赞/ 104 阅读

相关【LGP5350】序列

[题目][Link 1] 可能\\(\\operatorname\{fhq\\ treap\}\\)能做，但是珂朵莉树显然更好写珂朵莉树是个很玄学的东西啊，就是直接使用\

深藏阁楼爱情的钟/ 2023年10月11日 11:18/ 0 赞/ 19 阅读

相关 LGP5495 Dirichlet 前缀和

[题目][Link 1] 不是很明白为什么要叫做模板考虑到\\(a\_i\\)能对\\(b\_j\\)产生贡献，当且仅当\\(a\_i=\\prod p\_k^\{a\_

朱雀/ 2023年10月11日 11:16/ 0 赞/ 30 阅读

相关 18927 前缀和

题目描述前缀和是一种重要的预处理方法，能极大地降低查询序列区间和的时间复杂度。现在一个序列中有n个整数，下标从1…n。有m个查询，每个查询给出一个区间的左右

蔚落/ 2022年11月13日 04:11/ 0 赞/ 197 阅读

相关 Leetcode——前缀和

[题目直通车][Link 1] 运用数学思想左边的和 = 总和 - 当前索引的值-右边的和题目要求两边相等，也就是左边的和 = 右边的和因此公式变成左

分手后的思念是犯贱/ 2022年10月24日 01:42/ 0 赞/ 190 阅读

相关 HDU 5495 LCS（数论）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5495 参考博客： http://blog.csdn.net/queue

小咪咪/ 2022年08月09日 01:59/ 0 赞/ 158 阅读

相关 Dirichlet Process和Hierarchical Dirichlet Process的理解（PPT）

本文作者：合肥工业大学管理学院钱洋 email：1563178220@qq.com 内容可能有不到之处，欢迎交流。未经本人允许禁止转载。 ![这里写图片描述]

柔光的暖阳◎/ 2022年05月29日 11:46/ 0 赞/ 160 阅读

相关 [LGP5115] Check,Check,Check one two!

> 神奇的思路，还是要学习一个。题意：给你一个字符串，并定义两个前缀的lcs、两个后缀的lcp，求式子膜\\(2^\{64\}\\)的值。 \\\[ \\sum\_\{

约定不等于承诺〃/ 2021年12月10日 05:27/ 0 赞/ 233 阅读