题目描述

原题地址：luogu

一句话题意：求$\sum_{i = l}^ri-\varphi(i)$。其中，$l,r\leq 10^{12}$

假的假的，世界都是假的

定理内容

关于$x,y$的二元一次方程$ax+by=m$有解，当且仅当$m$是$d$的整数倍，其中，$d=\gcd(a,b)$

读完上面这句话，你一定会觉得这是什么辣鸡定理，感觉好没用的样子。

其实裴蜀定理还用后半部分。

定理

设正整数 $m_1,m_2,⋯,m_n$ 两两互质，则同余方程组

$$ \begin{cases} x\equiv a_1(\mod m_1)&(1)\
x\equiv a_2(\mod m_2)&(2)\
\cdots\
x\equiv a_n(\mod m_n)&(n)\
\end{cases} $$

线性筛

普通筛法

这个大家都会，它效率低下的原因是一个数被重复筛去了。

GCD

求GCD一般使用欧几里得的算法，即$\gcd(a,b)=\gcd(b, a\mod b)$

然后就随便写写就好了，这个大家都会qwq

比赛地址：Codeforces

A

A题没什么好说的，大力膜你一下就好

题目描述

原题地址：COGS

题目是在济南集训时候的比赛题

题意：求$\sum^n_ {i = 1}\sum_{j=1}^m\gcd(i,j)\mod998244353$

数论

• 拓欧
• 线性筛
• 求欧拉函数
• 组合数

题目描述

原题地址：Codeforces

思路

固定两个相邻的点，其中一个是顶点，然后枚举另一个点的位置，求角。

观察到所成角每次增加$\frac{\pi}{n}$，然后就递推一波。。

题目描述

问题：题目地址 ，中文版

思路

注意到$a,b\leq 60$，所以预处理出所有$x^a,y^b$存起来，然后两两求和，去重， 然后处理一下得到答案。

坑点

1. 开unsigned long long

2. while (num <= 1e18)
      num = num * x
   

   这样写是不符合基本法的，会溢出掉的