容斥 C. Strange Function改编题

2023-11-21 16:01
文章标签 function 容斥 strange 改编

本文主要是介绍容斥 C. Strange Function改编题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

补题:

题目详情 - 9.段坤爱取模%%% - SUSTOJ

本题或许是参考 Problem - C - Codeforces

根据题意,f(i)就是不能被整除的最小的一个质因子。

打表发现,当15个质因子相乘后,长度就大于18。

image-20231119231908296

因此可以知道小于等于1e16内的正整数x,f(x)一定是前20个质因子之一,且合数一定不行。

前20个质因子:2 3 5 7 11 13 17 19 23 29 31 37 41 43 。在第15个质因子相乘时就大于1e16,因此max(f(i))是小于40的。

现在就是要求:第1个质因子在[l, r]的个数 乘上 第1个质因子,加上 第2个质因子在[l, r]的个数 乘上 第2个质因子个数, … 。需要保证i在[l, r]内仅且一次被计算。考虑容斥。

对于f(i) = k来说,i可以被1 ... k - 1任何一个整除,但是不能被k整除。

f()值为k的个数有:
⌊ r l c m ( 1 , . . . k − 1 ) − r l c m ( 1 , . . . k ) ⌋ − ⌊ l l c m ( 1 , . . . k − 1 ) − l l c m ( 1 , . . . k ) ⌋ \lfloor { \frac {r} {lcm(1, ... k-1)} } - { \frac {r} {lcm(1, ... k)} } \rfloor - \lfloor { \frac {l} {lcm(1, ... k-1)} } - { \frac {l} {lcm(1, ... k)} } \rfloor lcm(1,...k1)rlcm(1,...k)rlcm(1,...k1)llcm(1,...k)l
如果将[l, r]分成两部分[1, l][1, r]来处理的话。

以r为例,f()为k的个数:
⌊ r l c m ( 1 , . . . k − 1 ) − r l c m ( 1 , . . . k ) ⌋ \lfloor { \frac {r} {lcm(1, ... k-1)} } - { \frac {r} {lcm(1, ... k)} } \rfloor lcm(1,...k1)rlcm(1,...k)r
那么,[1, r]sum就是:
∑ k ≥ 2 k × ( ⌊ r l c m ( 1 , . . . k − 1 ) − r l c m ( 1 , . . . k ) ⌋ ) = 2 × ( r − ⌊ r l c m ( 1 , 2 ) ⌋ ) + 3 × ( ⌊ r l c m ( 1 , 2 ) − r l c m ( 1 , 2 , 3 ) ⌋ ) + . . . = r + ∑ k ≥ 1 ⌊ r l c m ( 1 , . . . , k ) ⌋ \sum_{k \ge 2}k \times(\lfloor { \frac {r} {lcm(1, ... k-1)} } - { \frac {r} {lcm(1, ... k)} } \rfloor) \\ = 2 \times (r - \lfloor \frac r {lcm(1,2)} \rfloor) + 3 \times (\lfloor { \frac {r} {lcm(1,2)} } - { \frac {r} {lcm(1,2,3)} } \rfloor) + ... \\ = r + \sum_{k \ge 1} \lfloor \frac r {lcm(1, ..., k)} \rfloor k2k×(⌊lcm(1,...k1)rlcm(1,...k)r⌋)=2×(rlcm(1,2)r⌋)+3×(⌊lcm(1,2)rlcm(1,2,3)r⌋)+...=r+k1lcm(1,...,k)r
同理,可得[1, l]内的sum,两者相减即为答案。对于cf上的C,[1, r]即可。

时间复杂度:前面稠密,后面稀疏,最大为O(41 * 2)

const int mod = 998244353;
// https://codeforces.com/contest/1542/problem/C
void solve() {int l,r; cin>>l>>r;int sum = 0;int v = 1;auto lcm = [&](int a, int b) {return a * b / __gcd(a,b);};for(int i = 1; v <= r; v = lcm(i, v), ++i) {sum = (sum + r / v) % mod;}v = 1;for(int i = 1; v <= l - 1; v = lcm(i,v), ++i) {sum = (sum - (l - 1) / v + mod) % mod;}cout<<sum<<endl;
}

总结

赛时对这题容斥没有找到切入点。这个容斥处理极具有思维性,还是需要多做思维题!

参考:

[Codeforces] number theory (R1600) Part.11 - 知乎 (zhihu.com)

Submission #121200660 - Codeforces

这篇关于容斥 C. Strange Function改编题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/403418

相关文章

hdu4407(容斥原理)

题意:给一串数字1,2,......n,两个操作:1、修改第k个数字,2、查询区间[l,r]中与n互质的数之和。 解题思路:咱一看,像线段树,但是如果用线段树做,那么每个区间一定要记录所有的素因子,这样会超内存。然后我就做不来了。后来看了题解,原来是用容斥原理来做的。还记得这道题目吗?求区间[1,r]中与p互质的数的个数,如果不会的话就先去做那题吧。现在这题是求区间[l,r]中与n互质的数的和

hdu4407容斥原理

题意: 有一个元素为 1~n 的数列{An},有2种操作(1000次): 1、求某段区间 [a,b] 中与 p 互质的数的和。 2、将数列中某个位置元素的值改变。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.Inpu

hdu4059容斥原理

求1-n中与n互质的数的4次方之和 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWrit

AutoGen Function Call 函数调用解析(一)

目录 一、AutoGen Function Call 1.1 register_for_llm 注册调用 1.2 register_for_execution 注册执行 1.3 三种注册方法 1.3.1 函数定义和注册分开 1.3.2 定义函数时注册 1.3.3  register_function 函数注册 二、实例 本文主要对 AutoGen Function Call

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

(function() {})();只执行一次

测试例子: var xx = (function() {     (function() { alert(9) })(); alert(10)     return "yyyy";  })(); 调用: alert(xx); 在调用的时候,你会发现只弹出"yyyy"信息,并不见弹出"10"的信息!这也就是说,这个匿名函数只在立即调用的时候执行一次,这时它已经赋予了给xx变量,也就是只是

js私有作用域(function(){})(); 模仿块级作用域

摘自:http://outofmemory.cn/wr/?u=http%3A%2F%2Fwww.phpvar.com%2Farchives%2F3033.html js没有块级作用域,简单的例子: for(var i=0;i<10;i++){alert(i);}alert(i); for循环后的i,在其它语言像c、java中,会在for结束后被销毁,但js在后续的操作中仍然能访

rtklib.h : RTKLIB constants, types and function prototypes 解释

在 RTKLIB 中,rtklib.h 是一个头文件,包含了与 RTKLIB 相关的常量、类型和函数原型。以下是该头文件的一些常见内容和翻译说明: 1. 常量 (Constants) rtklib.h 中定义的常量通常包括: 系统常量: 例如,GPS、GLONASS、GALILEO 等系统的常量定义。 时间常量: 如一年、一天的秒数等。 精度常量: 如距离、速度的精度标准。 2. 类型

【AI大模型应用开发】2.1 Function Calling连接外部世界 - 入门与实战(1)

Function Calling是大模型连接外部世界的通道,目前出现的插件(Plugins )、OpenAI的Actions、各个大模型平台中出现的tools工具集,其实都是Function Calling的范畴。时下大火的OpenAI的GPTs,原理就是使用了Function Calling,例如联网检索、code interpreter。 本文带大家了解下Function calling,看

容斥问题

一、填空题 1.一个班有45个小学生,统计借课外书的情况是:全班学生都借有语文或数学课外书.借语文课外书的有39人,借数学课外书的有32人.语文、数学两种课外书都借的有     人. 3.在1~100的自然数中,是5的倍数或是7的倍数的数有     个. 4.某区100个外语教师懂英语或俄语,其中懂英语的75人,既懂英语又懂俄语的20人,那么懂俄语的教师为     人. 5.六一班