111qqz的小窝

老年咸鱼冲锋!

BZOJ 2257: [Jsoi2009]瓶子和燃料 (裴蜀定理)

2257: [Jsoi2009]瓶子和燃料 Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1246 Solved: 756 [Submit][Status][Discuss] Description jyy就一直想着尽快回地球,可惜他飞船的燃料不够了。 有一天他又去向火星人要燃料,

codeforces #382 div2 D. Taxes(哥德巴赫猜想)

题目链接 题意:一个人有n元前,他要交的税是n的最大因子(除n外),现在这个投机倒把者想把前分成k部分(k为大于等于1的任意值)每部分不能为1

uva 10692 Huge Mods (欧拉函数,指数循环节)

题目链接 题意:求一个楼梯数%m的大小。 思路:指数循环节。 需要注意的是,模数只有最外层是m,每往里一层,模数都变成m=phi(m) 所以可以写个

hdu 4704 Sum (隔板法,指数循环节,费马小定理)

题目链接 题意:定义s(k)为将n分成k个正整数的划分数,给出n,问s(1) + s(2) + … + s(n-1) + s(n)是多少,结果9+7,其中n<=10^1

hdu 4549 M斐波那契数列 (矩阵快速幂+费马小定理+指数循环节)

题意:M斐波那契数列F[n]是一种整数数列,它的定义如下: F[0] = a F[1] = b F[n] = F[n-1] * F[n-2] ( n > 1 ) 现在给出a, b, n,你能求出F[n]的值吗? 思路:观

指数循环节学习笔记

资料先行: 指数循环节证明 指数循环节2 对指数循环节的一些理解 挂了一点题目,写完来写总结。 vjudge_不会指数循环节的111qqz 写完了。 首先

poj 2891 Strange Way to Express Integers (扩展欧几里得算法解一般线性同余方程组)

题目链接 题意:给出k个方程,形式为 x==r1,求最小的正数x,无解输出-1. 思路:首先很容易让人联想到crt. 然而crt的使用条件是,所有的

poj 1006 Biorhythms (中国剩余定理模板题)

题目链接: **题意:**人自出生起就有体力,情感和智力三个生理周期,分别为23,28和33天。一个周期内有一天为峰值,在这一 天,人在对应的方

poj 2142 The Balance (扩展欧几里得算法)

题目链接 题意:给出a,b,d,分别表示a,b两种刻度的砝码,以及要称量的物体重量为d.现在保证能称量出给定重量的物体,问两种砝码个数的和最小

poj 2115 C Looooops (扩展欧几里得算法)

题目链接 题意: 问 循环for ( int i = a ; i !=b; i+=c)在% (2^k)的意义下循环了多少次。 思路: 一般的思路是: 列方程… 化成扩展欧

hdu 2669 Romantic (扩展欧几里得模板题)

题目链接 题意:问ax+by=1的一组x>0的解,如果无解输出sorry. 思路:根据裴蜀定理, ax+by=1有解当且gcd(a,b)=1

中国剩余定理(crt)学习笔记

前置技能点: 维基百科_裴蜀定理(贝祖等式) 对任何[整数](https://zh.wikipedia.org/wiki/)![a](https

二次剩余(Cipolla's algorithm)学习笔记

先放资料。 前置技能点: 剩余系 剩余系**:****设模为****m,****则根据余数可将所有的整数分成****m****类,分别记成****

bestcoder #88 || hdu 5908 Abelian Period(暴力)

题目链接 题意:一段数字串,如果一个数字k满足,将该串分成若干个长度为K的子串,这些子串两两满足每个字符出现的次数一样多,那么称为k是一个阿贝

codeforces 594 D. REQ (树状数组+欧拉函数+逆元)

题目链接 题意:给出n个数,q个查询,每组一个区间,询问区间中所有数的乘积的欧拉函数9+7的答案是多少。 思路:这道题需要一点欧拉函数的知识。 p

bzoj 1053: [HAOI2007]反素数ant

1053: [HAOI2007]反素数ant Time Limit: 10 Sec Memory Limit: 162 MB Submit: 2750 Solved: 1559 [Submit][Status][Discuss] Description 对于任何正整数x,其约数的个数记作g(x)。例如g(1)=1、g(6)=4。如

codeforces 27 E. Number With The Given Amount Of Divisors (dfs,反素数(假))

题目链接 题意:求约数个数恰好为n个的最小的x 思路:这道题是作为反素数的例题出现在acdreamer的博客里的。 但是实际上,这道题应该和反素数

hdu 2521 反素数

题目链接 题意:求区间[a,b]中约数最多的那个数,如果有多个,输出最小的。 思路:看起来好像和反素数没什么关系…只是打个约数个数

反素数学习笔记

acdreamer的博客 wiki上的反素数是什么鬼orz…完全不是一个东西吧。。。。 反素数直观得理解。。。就是一个约数特别多的

codeforces 474 F. Ant colony (线段树求gcd+统计区间中某数出现的次数的经典做法)

题目链接 题意:给出n个数,m个查询,每组查询一个区间[l,r],问[l,r]中会被吃掉多少个(区间[l,r]中的数只有当其是其他所有数的因数