Hi_archer

自己选择的路,跪着也要走完

bzoj2693 jzptab 莫比乌斯反演+整除分块

\begin{gather*} &ans=\sum^{n}_{i=1}\sum^{m}_{j=1}\frac{ij}{gcd(i,j)}\\ &ans=\sum^{n}_{d=1}\sum^{m}_{i=1}\sum^{n}_{j=1}\frac{ij}{d}[gcd(i,j)==d]\\ &ans=\sum^{n}_{d=1}\frac{1}{d}\sum^{m}_{i=1}i\sum^{...

  • 285484026
  • May 23, 2019
  • No comments
    •

    Codeforces Round #556

    Div2.A：Stock Arbitraging题解：简单题#include<bits/stdc++.h> using namespace std; int n,m,r,Min = 2147483647,Max; int main(){ scanf("%d %d %d",&n,&m,&r); int x; ...

  • 285484026
  • May 4, 2019
  • No comments
    •

    bzoj 3309 DZY Loves Math 莫比乌斯函数反演 整除分块

    问题为：然后就可以用线性筛递推以后用整数分块计算答案。#include <bits/stdc++.h> const int MAXN = 1e7; using namespace std; int T,n,m,cnt; int p[MAXN+5],g[MAXN+5],a[MAXN+5],b[MAXN+5]; bool vis[MAXN+5]; inline void in...

  • 285484026
  • April 26, 2019
  • No comments
    •

    [2019南昌网络赛] tsy's number 莫比乌斯反演 整除分块 积性函数递推

    问题为： \begin{align*} 若k != 1\ g(p) &= p^k-p^{k-1}-(p^{k-1}-p^{k-2})\\ g(p) &= p^k-2p^{k-1}+p^{k-2}\\ g(p) &= (p-1)^2p^{k-2}\\ \end{align*}这样的话就可以用线性筛递推求得g(n)#include <bits/stdc++.h> const int...

  • 285484026
  • April 23, 2019
  • 1 comments
    •

    【NOI2010】 超级钢琴 线段树+堆

    [2006: [NOI2010]超级钢琴][1]一句话题意：计算出所有区间和中前K大题解：显然根据题目要求我们需要在$O(NlogN)$的时间复杂度内解决这个问题。首先我们枚举左端点L，然后设区间右端点处在[qL,qR]这个区间。我们需要在$O(logN)$的时间复杂度内计算出从左端点到右端点区间和的最大值。如何快速的计算出这个最大值以及最大值所在的位置呢？预处理出前缀和，这样的话我们上述问...

  • 285484026
  • April 12, 2019
  • No comments