定理内容

关于$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 an(\mod m_n)&(n)\
\end{cases} $$ 有整数解,且在模$M=\prod
{i=1}^n m_i$下解唯一。为:

阅读全文

线性筛

普通筛法

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

阅读全文

GCD

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

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

阅读全文

题目描述

原题地址: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
    

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

阅读全文

普通的快速幂

问题[COGS 1433]圣庙里的汉诺塔

计算$a^b\mod m$,其中$0\leq a,b\leq10^{16}$。

我们可以写出如下的暴力求幂程序,复杂度$O(n)$:

typedef long long ll;
ll pow_mod(ll a,ll b,ll m)
{
  	ll ans=1;
  	while(b--)
      	ans=(ans*a)%m;
  	return ans;
}

不过注意到对于任意正整数k,我们都可以拆成至多$log k$个二进制下的1,所以我们可以计算出$a^{2^0},a^{2^1},a^{2^2},\cdots$(可以递推出来),然后再用$\log b$次乘法将其合并起来,复杂度为$O(\log n)$,代码如下:

ll fast_pow_mod(ll a,ll b,ll m)
{
    ll ans=1;
  	while(b)
    {
      	if(b&1)
          	ans*=a;
      	a*=a;
      	b>>=1;
    }
  	return ans;
}

由快速幂魔改的快速乘

问题:[COGS 2037]Asm.def大点兵

由于$a\times b$可能溢出,因此不能直接乘起来再取膜,考虑到一个事实: $$ a^b= \begin{cases}

1 & b=0 \\
\underbrace { a \times \cdots \times a }_b & b \ge 1

\end{cases} $$ $$ a\times b= \begin{cases} 0&b=0
\underbrace{a+\cdots+a}_b&b\not=0 \end{cases} $$ 所以我们把上面的代码稍微改一改就好了:

阅读全文