标签归档:整除分块

LightOJ – 1245 Harmonic Number (II)

LightOJ - 1245

整除分块裸题.

BZOJ 1257-余数之和里有应用过,推理部分也在那篇文章里,或者直接看《算法竞赛进阶指南》P139.

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#define maxn 0x3f3f3f3f
#define ll long long
using namespace std;

long long H( int n ) {
    long long res = 0;
    int len;
    for( long long i = 1; i <= n; i+=len ){
        len=n/(n/i)-i+1;
        res = res + (n / i)*len;
    }
    return res;
}

int main() {
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int T,kase=0;
  cin>>T;
  while(T--){
      int n;
      cin>>n;
      printf("Case %d: %lld\n",++kase,H(n));
  }
  return 0;
}

BZOJ 1257-余数之和

题目:

给定正整数 \(n\)和 \(k\),计算\((k\mod 1)+(k\mod 2)+...+(k\mod n)\)的值.\(1<=n,k<=10^9\).

思路:
直接暴力求果断TLE了.所以需要适当转化,降低时间复杂度.

整个式子可以转化为\( n*k-\sum_{i=1}^n\lfloor k/i\rfloor *i\) .

对于任意整数 \( x\in [1,k]\),设 \(g(x)=\lfloor k/\lfloor k/x\rfloor \rfloor\),有\(g(x)>=\lfloor k/(k/x)\rfloor =x\), 故\( \lfloor k/g(x)\rfloor <=\lfloor k/x \rfloor\).
另有,\(\lfloor k/g(x) \rfloor >=\lfloor k/(k/\lfloor k/x \rfloor ) \rfloor = \lfloor k/k* \lfloor k/x \rfloor \rfloor = \lfloor k/x \rfloor \) ,故\( \lfloor k/g(x) \rfloor =\lfloor k/x \rfloor \).

所以,\( \forall i \in [x,\lfloor k/ \lfloor k/x \rfloor \rfloor ],\lfloor k/i \rfloor \) 的值都相等.

\( \forall i \in [1,k] ,\lfloor k/i \rfloor \) 至多只有\(2*\sqrt{k}\)个不同的值.当\( i<= \sqrt{k}\) 时, \( \lfloor k/i \rfloor \)至多只有 \( \sqrt{k} \)个不同的值,而当\( i> \sqrt{k} \)时, \( \lfloor k/i \rfloor < \sqrt{k} \) ,故\( \lfloor k/i \rfloor \)也至多只有 \( \sqrt{k} \)个不同的值.

综上所述,对于 \( i \in [1,k] \) ,\( \lfloor k/i \rfloor \)由不超过\( 2*\sqrt{k} \)段组成,每一段 \( i \in [x, \lfloor k/ \lfloor k/x \rfloor \rfloor] \)中 \(\lfloor k/i \rfloor\)的值都等于\(\lfloor k/x \rfloor\). \( i*\lfloor k/i \rfloor\) 在段中,就是公差为\( \lfloor k/x \rfloor \)的等差数列.
整个算法时间复杂度为O(\(\sqrt{k}\)).

代码:

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>

using namespace std;
#define MAX_N 2e9

typedef  long long ll;
typedef  unsigned long long ull;

int main() {
  ll n ,k;
  cin>>n>>k;
  ll ans=n*k;;
  for(ll l=1,r;l<=n;l=r+1){
     r=k/l? min(k/(k/l),n):n;
     ans-=(k/l)*(l+r)*(r-l+1)/2;
  }
  cout<<ans<<endl;
  return 0;
}