数论 – Tgotp-Blog

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-5ad8ce3b1049a195[......]

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

1257: [CQOI2007]余数之和sum

没考虑i的longlong wa了半天。。。

推推式子我们即可知道答案等于:

Ans=k*n-∑(k/i)*i

( i , n/(n/i) )中所有的 k/i 结果都是一样的。

然后对于k/i相同的区间用下等差数列的求和公式搞搞就好了

然后k,n我倒了一下。。。一开始看[......]

Read more

P1134 阶乘问题

反正肯定知道高位数的答案肯定对结果没影响,所以取适当的位数取模就搞定了。。。

取模数完全靠猜。。。

c++代码如下: