OI教程之数学入门

\author{张若天}
\institute{清华大学}
\date{\today}

附属于/oi

推荐网站projecteuler.net

快速幂

$a^b \ mod \ c$, $a,b,c \le 10^9$

1
2
3
4
5
6
7
8
9
LL pow(LL a, LL b, LL p){
LL ret = 1%p;
while(b){
if(b&1) ret = ret*a%p;
b>>=1;
a=a*a%p;
}
return ret;
}

慢速乘

$a*b \ mod \ c$,$a,b,c \le 10^18$

1
2
3
4
5
6
7
8
9
LL mul(LL a, LL b, LL p){
LL ret = 0;
while(b){
if(b&1) ret = (ret+a)%p;
b>>=1;
a=(a+a)%p;
}
return ret;
}

例题:NOIP 2013 转圈游戏

n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏。按照顺时针方向给 n 个位置编号,从 0 到 n-1。最初,第 0 号小伙伴在第 0 号位置,第 1 号小伙伴在第 1 号位置,…,依此类推。
游戏规则如下:每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置,第 1 号位置小伙伴走到第 m+1 号位置,…,依此类推,第n − m号位置上的小伙伴走到第 0 号位置,第 n-m+1 号位置上的小伙伴走到第 1 号位置,…,第 n-1 号位置上的小伙伴顺时针走到第 m-1 号位置。
现在,一共进行了 $10^k$ 轮,请问 x 号小伙伴最后走到了第几号位置。

高精度计算

  • 大数字的存储: 用int数组,倒序存储。
  • 加法运算: 模仿列竖式。
  • 乘法运算: 模仿列竖式。

进制转换

  • 从base进制转当前(运算)进制: 展开为 $a_i\times base^i$ 求和。
  • 从当前(运算)进制转base进制: 1)整数部分:除base取余,倒序输出。2)小数部分:乘base取整,顺序输出。
  • $2^k$进制互转

Pick定理

一个计算顶点在格点上的多边形面积公式:
$$ S = a+\frac{b}{2} -1 $$

POJ 2954: gcd + Pick定理

分治乘法

$(a+bx)(c+dx) = ac + adx +bcx +bdx^2$
$(a+b)(c+d) = ac+ad+bc + bd$
递归。
四次乘法-> 三次乘法。
$O(n^{\log_2(3)})$

任何形式的使用、转载请注明出处!

更新于 2019年11月29日
评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框