[BZOJ1876][SDOI2009]superGCD（高精度）
题目：http://www.lydsy.com:808/JudgeOnline/problem.php?id=1876分析：以为辗转相减会TLE呢……但是好像没这个数据……就这么水过去了……辗转相减求a,b的gcd其实可以优化的：1、若a为偶数，b为奇数：gcd(a,b)=gcd(a/2,b)2、若...
bzoj 1876 [SDOI2009]SuperGCD（高精度+更相减损）
1876: [SDOI2009]SuperGCDTime Limit: 4 Sec Memory Limit: 64 MBSubmit: 2384 Solved: 806[Submit][Status][Discuss]DescriptionSheng bill有着惊人的心算能力，甚至能用大脑计...
BZOJ1876：[SDOI2009]SuperGCD——C++高精度良心题解
http://www.lydsy.com/JudgeOnline/problem.php?id=1876DescriptionSheng bill有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的GCD（最大公约 数）！因此他经常和别人比赛计算GCD。有一天Sheng bill很嚣张地找到了你，并...
【[SDOI2017]数字表格】
求\[Ans=\prod_{i=1}^N\prod_{j=1}^MFib[(i,j)]\]连乘的反演，其实并没有什么不一样我们把套路柿子拿出来\[F(n)=\sum_{i=1}^N\sum_{j=1}^M[n|(i,j)]=\left \lfloor \frac{N}{n} \right \rflo...
【洛谷4070】 [SDOI2016]生成魔咒（SAM）
传送门洛谷Solution考虑要求的是什么，前缀的本质不同的字符串个数？如果只要求一个串那么显然答案是\(\sum_{i=1}^{tot}len[i]-len[fa[i]]\)（实际上这个并不显然，想一想为什么）接着就是在线的啦，你可别忘了SAM本身就是在线算法，每一次算一个贡献就好了。代码实现代码...
BZOJ 1974: [Sdoi2010]auction 代码拍卖会( dp )
在1, 11, 111……中选<=8个, + 11..(n个1)拼出所有可能...这些数mod p至多有p中可能, 找出循环的处理一下. 那么dp就很显然了...dp(i, j, k)表示前i种选出了j个, 组合出的数mod p = k, 然后递推一下就好了.-----------------...
【题解】SDOI2014旅行
洛谷P3313大概是一道树链剖分的裸题。可以看出如果不是查询相同宗教的这一点，就和普通的树链剖分毫无两样了。所以针对每一个宗教都单独开一棵线段树，变成单点修改+区间查询。只不过宗教数目很多，空间消耗太大所以只能开一棵总的再动态开点。#include <bits/stdc++.h>usin...
【BZOJ 3529】 [Sdoi2014]数表 （莫比乌斯+分块+离线+树状数组）
3529: [Sdoi2014]数表Description有一张N×m的数表，其第i行第j列（1 < =i < =礼，1 < =j < =m）的数值为能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。Input输入包含多组数据。 输入的第一行一个整数...
BZOJ.2242.[SDOI2011]计算器(扩展欧几里得 BSGS)
同余方程都不会写了。。还一直爆int/*2.关于同余方程ax ≡b(mod p)，可以用Exgcd做，但注意到p为质数，y一定有逆元首先a%p=0时 仅当b=0时有解；然后有x ≡b*a^-1(mod p)，a,p互质，可用快速幂求a的逆元，*b的得到x但是扩欧还是比快速幂快的*/#include&...
[BZOJ 3530][Sdoi 2014]数数
阿拉~好像最近总是做到 AC 自动机的题目呢喵~题目的算法似乎马上就能猜到的样子…… AC 自动机 + 数位 dp先暴力转移出 f[i][j] ：表示从 AC 自动机上第 j 号节点走 i 步且不碰到匹配串的方案数然后直接用数位 dp 一位一位的试就可以了，大家都会吧~但是…… 有前导 0 的情况真...
BZOJ2190 [SDOI2008]仪仗队（欧拉函数）
与HDU2841大同小异。设左下角的点为(1,1)，如果(1,1)->(x,y)和(1,1)->(x',y')向量平行，那只有在前面的能被看见。然后就是求x-1、y-1不互质的数对个数。而x或y等于1可以另外讨论一下，就是当n不等于1时就有两个，n等于1就特判一下。那么就用欧拉函数计数了...
[BZOJ2186][Sdoi2008]沙拉公主的困惑（数论）
题目描述 传送门 题解 首先如果 (a,b)=1 ，则 (a+b,b)=1 因为n>m，所以m!|n! φ(m!) 表示1~m!中与m!互质的数的个数，那么如果将这些数都加上m!的倍数也一定与m!互质 所以答案为 φ(m!)∗n!m! ...
Bzoj2186 [Sdoi2008]沙拉公主的困惑
Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 4100 Solved: 1424 Description 大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为1到N的阶乘，但是，政府只发行编号与M!互质的钞票。...
[BZOJ2186][SDOI2008]沙拉公主的困惑（数论）
设 f[i] 表示 [1,i!] 的数中与 i! 互质的数的个数。边界为 f[0]=1 。 首先介绍一个性质：当 (a,x)=1 时， (k∗x+a,x)=1 。 当 i 不为质数时， (i−1)! ...
【数论】【欧拉函数】【筛法求素数】【乘法逆元】【快速幂取模】bzoj2186 [Sdoi2008]沙拉公主的困惑
http://www.cnblogs.com/BLADEVIL/p/3490321.html http://www.cnblogs.com/zyfzyf/p/3997986.html 翻了翻题解，这两个合起来比较明白…… 题意：求1~n!中与m!互质的数的数量(mod R)。 ∵由欧几里得算法得...
bzoj2186: [Sdoi2008]沙拉公主的困惑 逆元
传送门 题意：求1-n!中与m!互质的数的个数，其中m小于n。 思路：由于m小于n，所以n!一定是m!的倍数，小于m!与m!互质的数的个数为phi(m!)，所以1-n!中与m!互质的数的个数为n!/m!*phi(m!)=n!/m!*m!*(1-1/p1)*(1-1/p2)*...(1-1/pk) =...
【bzoj3530】[Sdoi2014]数数 AC自动机+数位dp
题目描述我们称一个正整数N是幸运数，当且仅当它的十进制表示中不包含数字串集合S中任意一个元素作为其子串。例如当S=(22，333，0233)时，233是幸运数，2333、20233、3223不是幸运数。给定N和S，计算不大于N的幸运数个数。输入输入的第一行包含整数N。接下来一行一个整数M，表示S中元...
[SDOI2015] 寻宝游戏
传送门：>Here<题意：给出一棵树（有边权），刚开始键值全部为0。每次对其中一个键值进行异或，问每一次修改之后：选择任意一个点出发走到所有为1的点再走回来的最短路解题思路由于N,M都是十万级别的，所以必须在线处理。很容易想到每次只需要对答案做出一点修改即可考虑现在有$k$的节点有宝藏，...
P2486 [SDOI2011]染色（树剖）区间覆盖+区间的连续段
https://www.luogu.org/problemnew/show/P2486值的一看https://www.cnblogs.com/Tony-Double-Sky/p/9283262.html分析：树剖后，线段树要记录左端点l,右端点r，左端点的颜色lc,右端点的颜色rc,区间成段更新的标...
【数位dp】bzoj3131: [Sdoi2013]淘金
思路比较自然，但我要是考场上写估计会写挂；好像被什么不得了的细节苟住了？……Description小Z在玩一个叫做《淘金者》的游戏。游戏的世界是一个二维坐标。X轴、Y轴坐标范围均为1..N。初始的时候，所有的整数坐标点上均有一块金子，共N*N块。 一阵风吹过，金子的位置发生了一些变化。细心的小...