c2c网站建设实例,北京网站如何做推广,怎样做网站卖东西 自己有货,怎么做订阅号文章目录前提知识复习T1#xff1a;余数求和titlesolutioncodeT2#xff1a;Ice RaintitlesolutioncodeT3#xff1a;The FooltitlesolutioncodeT4#xff1a;模积和titlesolutioncode前提知识复习
整除分块是用于快速处理形似下列式子的方法#xff0c;是解决莫比乌斯反…
文章目录前提知识复习T1余数求和titlesolutioncodeT2Ice RaintitlesolutioncodeT3The FooltitlesolutioncodeT4模积和titlesolutioncode前提知识复习
整除分块是用于快速处理形似下列式子的方法是解决莫比乌斯反演类题目需要掌握的前提知识 ∑i1n⌊ni⌋\sum_{i1}^n\lfloor\frac{n}{i}\rfloori1∑n⌊in⌋ 但是本篇博客的例题是特别特别板的不会涉及莫比乌斯反演请dalao们出门左转别浪费时间蟹蟹 回归正题很显然上面的式子可以O(n)O(n)O(n)得到答案 但是在某些题目中毒瘤出题人将数据加强到了 101010^{10}1010以上 这个时候我们就无法通过O(n)O(n)O(n) 的解法来得到答案 我们需要一个O(n)O(\sqrt{n})O(n)的更为优秀的解法
对于单一的⌊ni⌋\lfloor\frac{n}{i}\rfloor⌊in⌋某些地方的值是相同的并且呈块状分布 通过深入的探求规律与严密推理以及暴力打表与幸运瞎猜 最后惊奇的发现这些块状分布的值是有规律的 对于一个块假设它的起始位置的下标为lll那么可以得到的是它的结束位置的下标为 代码表示即为
r n / ( n / l );分块如果非要安排一个模板的话那就是一个forforfor循环了
int calc( int n ) {int ans 0;for( int l 1, r;l n;l r 1 ) {r n / ( n / l );//根据题目要求进行计算 }return ans;
}有的时候不同的题目可能出现n/l0n/l0n/l0的情况为了防止程序挂掉我们也可以这么写
int calc( int n ) {int ans 0;for( int l 1, r;l n;l r 1 ) {if( k / l ) r min( k / ( k / l ), n );else r n;//根据题目要求进行计算}return ans;
}具体的就用例题来体会吧
T1余数求和
title
添加链接描述
solution
G(n,k)∑i1nkmodi∑i1n(k−⌊ki⌋∗i)∑i1nk−∑i1n⌊ki⌋∗iG(n,k) ∑_{i1}^n k\ mod\ i\sum_{i1}^n(k-\lfloor\frac{k}{i}\rfloor*i)\sum_{i1}^nk-\sum_{i1}^n\lfloor\frac{k}{i}\rfloor*iG(n,k)i1∑nk mod ii1∑n(k−⌊ik⌋∗i)i1∑nk−i1∑n⌊ik⌋∗i 前面的求和式子可以很直观地得到∑i1nkn∗k\sum_{i1}^nkn*k∑i1nkn∗k 后面的求和式子我们令lll表示这个块的开始下标rrr为这个块的结束下标T⌊ni⌋T\lfloor\frac{n}{i}\rfloorT⌊in⌋则该块里面的值为 ∑ilrT∗i∑ilrT−∑ilri\sum_{il}^rT*i\sum_{il}^rT-\sum_{il}^riil∑rT∗iil∑rT−il∑ri 答案显而易见了吧第一个求和就是个定值(r−l1)∗T(r-l1)*T(r−l1)∗T后面的求和就是等差数列 计算方法首项加末项乘以项数除以二(lr)∗(r−l1)/2(lr)*(r-l1)/2(lr)∗(r−l1)/2 code
#include cstdio
#include iostream
using namespace std;
#define int long long
signed main() {int n, k;scanf( %lld %lld, n, k );int ans n * k;for( int l 1, r;l n;l r 1 ) {if( k / l ) r min ( k / ( k / l ), n );else r n;ans - ( r - l 1 ) * ( k / l ) * ( l r ) / 2;}printf( %lld, ans );return 0;
}T2Ice Rain
title
添加链接描述
solution
读完题后是不是 一模一样的吧这种sb题 你加一个无线输入操作就ACACACpasspasspass下一个
code
#include cstdio
#include iostream
using namespace std;int main() {long long n, k;while( ~ scanf( %lld %lld, n, k ) ) {long long ans n * k;for( long long l 1, r;l n;l r 1 ) {if( k / l ) r min( k / ( k / l ), n );else r n;ans - ( k / l ) * ( l r ) * ( r - l 1 ) / 2;}printf( %lld\n, ans );}return 0;
}T3The Fool
title
添加链接描述
solution
一样的吧差不多的吧如果你没有一点思路的话证明我写的太差 没有学懂哦~ ∑i1n⌊ni⌋∑_{i1}^n \lfloor\frac{n}{i}\rfloor∑i1n⌊in⌋先分出每个块然后再等差数列求和加在一起最后判断vanvanvan事
code
#include cstdio
int main() {int T;scanf( %d, T );for( int Case 1;Case T;Case ) {long long n;scanf( %lld, n );long long ans 0;for( int l 1, r;l n;l r 1 ) {r n / ( n / l );ans ( r - l 1 ) * ( n / l );} if( ans 1 ) printf( Case %d: odd\n, Case );else printf( Case %d: even\n, Case );}return 0;
}T4模积和
title
添加链接描述
solution
这道题就是个重头戏了其实也很简单的 仔细看推导过程 ans∑i1n∑j1m(nmodi)×(mmodj),i≠jans∑_{i1}^n∑_{j1}^m(n\ mod\ i)×(m\ mod\ j),i≠jansi1∑nj1∑m(n mod i)×(m mod j),ij 用容斥拆开把ijijij的情况减掉即可 ans∑i1n∑j1m(nmodi)×(mmodj)−∑i1min(n,m)(nmodi)×(mmodi)ans∑_{i1}^n∑_{j1}^m(n\ mod\ i)×(m\ mod\ j)-∑_{i1}^{min(n,m)}(n\ mod\ i)×(m\ mod\ i)ansi1∑nj1∑m(n mod i)×(m mod j)−i1∑min(n,m)(n mod i)×(m mod i) 直接把显而易见能分块的先分了来再暴力展开 ∑i1n(nmodi)∑i1nn−∑i1n⌊ni⌋∗i∑_{i1}^n(n\ mod\ i)\sum_{i1}^nn-\sum_{i1}^n\lfloor\frac{n}{i}\rfloor*ii1∑n(n mod i)i1∑nn−i1∑n⌊in⌋∗i ∑j1m(mmodj)∑j1mm−∑j1m⌊mj⌋∗j∑_{j1}^m(m\ mod\ j)\sum_{j1}^mm-\sum_{j1}^m\lfloor\frac{m}{j}\rfloor*jj1∑m(m mod j)j1∑mm−j1∑m⌊jm⌋∗j ∑i1min(n,m)(nmodi)×(mmodi)∑i1min(n,m)(n−⌊ni⌋∗i)∗(m−⌊mi⌋∗i)∑_{i1}^{min(n,m)}(n\ mod\ i)×(m\ mod\ i)\sum_{i1}^{min(n,m)}(n-\lfloor\frac{n}{i}\rfloor*i)*(m-\lfloor\frac{m}{i}\rfloor*i)i1∑min(n,m)(n mod i)×(m mod i)i1∑min(n,m)(n−⌊in⌋∗i)∗(m−⌊im⌋∗i) ∑i1min(n,m)(nm⌊mi⌋⌊ni⌋i2−⌊mi⌋i−⌊ni⌋i)\sum_{i1}^{min(n,m)}(nm\lfloor\frac{m}{i}\rfloor\lfloor\frac{n}{i}\rfloor i^2-\lfloor\frac{m}{i}\rfloor i-\lfloor\frac{n}{i}\rfloor i)i1∑min(n,m)(nm⌊im⌋⌊in⌋i2−⌊im⌋i−⌊in⌋i) 整理综上 ans(∑i1nn−∑i1n⌊ni⌋∗i)(∑i1mm−∑i1m⌊mi⌋∗i)−∑i1min(n,m)(nm⌊mi⌋⌊ni⌋i2−⌊mi⌋i−⌊ni⌋i)ans(\sum_{i1}^nn-\sum_{i1}^n\lfloor\frac{n}{i}\rfloor*i)(\sum_{i1}^mm-\sum_{i1}^m\lfloor\frac{m}{i}\rfloor*i)-\sum_{i1}^{min(n,m)}(nm\lfloor\frac{m}{i}\rfloor\lfloor\frac{n}{i}\rfloor i^2-\lfloor\frac{m}{i}\rfloor i-\lfloor\frac{n}{i}\rfloor i)ans(i1∑nn−i1∑n⌊in⌋∗i)(i1∑mm−i1∑m⌊im⌋∗i)−i1∑min(n,m)(nm⌊im⌋⌊in⌋i2−⌊im⌋i−⌊in⌋i) 最后我们发现i2i^2i2在分块的时候挂掉了OMG怎么办告诉你一个结论 ∑ini2n∗(n1)∗(2n1)/2∑_i^ni^2n∗(n1)∗(2n1)/2i∑ni2n∗(n1)∗(2n1)/2 最后注意避雷ppp不是个质数稍微用随便找个互质的数搞个逆元就好了
code
#include cstdio
#include iostream
using namespace std;
#define int long long
#define mod 19940417
int n, m, inv;int qkpow( int x, int y ) {int ans 1;while( y ) {if( y 1 ) ans ans * x % mod;x x * x % mod;y 1;}return ans;
}int sqr( int x ) {return x * ( x 1 ) % mod * ( x 1 | 1 ) % mod * inv % mod;
}int sum( int l, int r ) {return ( l r ) * ( r - l 1 ) / 2 % mod;
}int calc( int n ) {int ans 0;for( int l 1, r;l n;l r 1 ) {r n / ( n / l );ans ( ans n * ( r - l 1 ) % mod - ( n / l ) * sum( l, r ) % mod mod ) % mod;}return ans;
}signed main() {inv qkpow( 6, 17091779 );scanf( %lld %lld, n, m );int ans calc( n ) * calc( m ) % mod;if( n m ) swap( n, m );for( int l 1, r;l n;l r 1 ) {r min( n / ( n / l ), m / ( m / l ) );int sum1 n * m % mod * ( r - l 1 ) % mod;int sum2 ( n / l ) * ( m / l ) % mod * ( sqr( r ) - sqr( l - 1 ) mod ) % mod;int sum3 ( n / l * m % mod m / l * n % mod ) * sum( l, r ) % mod;ans ( ans - ( sum1 sum2 - sum3 mod ) % mod mod ) % mod;}printf( %lld, ans );return 0;
}走了题还没做完…
