数论 – Tgotp-Blog

3293: [Cqoi2011]分金币

蓝书经典例题,详见蓝书前几页

c++代码如下:

 

2186: [Sdoi2008]沙拉公主的困惑

答案为 \frac{n!}{m!}*m!*(\frac{prime_i-1}{prime_i}) (mod\ p)

那么预处理即可,然后用快速幂算逆元

c++代码如下:

 

2956: 模积和

以为是个大水题。。。
结果写了两小时
我数学真差.jpg
容易发现式子可以化成

然后拆开可以得到(四个)五个式子,分别计算即可…
(懒得写公式了,自己推一下吧
然后你就能发现死活过不去…
原因是啥呢…给的这个模数竟然不是个质数。
那么考虑用exgcd来求解逆元就行了[......]

Read more

4403: 序列统计

首先,将不下降序列改为递增序列(即位置i得位置值再加i ,即可保证是递增序列。

然后数得范围就是2 ~ m + M - 1,方案数即为C(M + i  - 1,i)

那么答案即为∑(i=1,n) C(i - 1,M + i - 1)

考虑数据范围1e9 ,那么套用lucas定理。[......]

Read more

3884: 上帝与集合的正确用法

c++代码如下:

 

NOIP2017 题解

终于开始在晚自习的时候填填noip的坑了。

D1T1传送门

D1T2传送门

D1T3传送门

D2T1传送门

D2T2传送门

D2T3传送门

d1t1:math :

推规律(找规律),a*b-a-b;

c++代码如下:[......]

Read more

P3938 斐波那契

死于没开long long

打表观察发现 除了一号兔子以外,以后每月产生的兔子为斐波那契数列的个数。

所以前60项左右就会兔子总数就会达到1e12,然后其父亲为该id - 此时的sum[fi],所以跑一跑就好了。

c++代码如下:
[crayon-5b74fa035e3e4534[......]

Read more

1045: [HAOI2008] 糖果传递

均分纸牌的模型,详细见蓝书第三页
c++代码如下:

 

1053: [HAOI2007]反素数ant

一开始并没有理解到这个必须是严格小于,wa了多次...

很容易发现一个数的约数个数等于分解质因数后(pi+1)之积,然后分解的时候必须保证对于某一个因数个数求得最小的数,然后取最大约数个数的最小值.

所以必须满足前一个的pi < pj时 pi个数 >= pj个数

c++[......]

Read more

1192: [HNOI2006]鬼谷子的钱袋&&P2320 [HNOI2006]鬼谷子的钱袋

似乎洛谷的要难点,洛谷还要输出方案数。

跟以前我见过的某道题比较像,一个思想是,令f[i]为组合i的最少话费,那么下一次只用取的时候袋子就只用是i +1个,然后这题要袋子数量尽量少,那么只用倒序搞一搞就好了

c++代码如下:

Read more