题目：

给定正整数 \(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;
}

题目：

对于任何正整数x，其约数的个数记作\(g(x)\)。例如\(g(1)=1\)、\(g(6)=4\)。如果某个正整数x满足：\(g(x)>g(i)\) \(（0<i<x）\)，则称x为反质数。例如，整数 \(1，2，4，6\)等都是反质数。现在给定一个数 \(N（1<=N<=2*10^9）\)，求出不超过N的最大的反质数.

思路：
引理1: 1~N中最大的反质数，就是1~N中约数个数最多的数中最小的一个.（由定义易得）
引理2: 1~N中任何数的不同质因子都不会超过10个，且所有质因子的指数总和不超过30.
\((2*3*5*7*11*13*17*19*23*29*31>2*10^9\),即使只包含最小的质数，仍有 \(2^{31}>2*10^9)\)
引理3：x为反质数的必要条件是，x可写作\(2^{c_1}*3^{c_2}*5^{c_3}*7^{c_4}*11^{c_5}*13^{c_6}*17^{c_7}*19^{c_8}*23^{c9}*29^{c{10}}\),并且\(c_1>=c2>...>=c{10}>=0\) (由反证法可得)
综上，可通过dfs求出各个\(c_1,c_2...c_n\) ,搜索过程中根据上述限制要求进行剪枝。
约数个数为\((c_1+1)*(c_2+1)*...*(cn+1)=\prod{i=1}^{n}(c_i+1)\) .
由引理1确定最后结果。

代码：

#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 prime[12]={2,3,5,7,11,13,17,19,23,29,31};
ll ans;
ll acnt;
ll n;

void dfs(ll x,ll cnt,int step){
    if(step==11){
       if((x>ans&&cnt>acnt)||x<=ans&&cnt>=acnt){
          acnt=cnt;
          ans=x;
       }
       return ;
    }
    ll P=1;
    for(int i=0;i<31;i++){
      if(x*P>n) break;
      dfs(x*P,cnt*(i+1),step+1);
      P*=prime[step];
    }
}

int main() {
  cin>>n;
  dfs(1,1,0);
  printf("%d\n",ans);
  return 0;
}

题目：

给定整数 N(1≤N≤10^6)，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的p_i 和 c_i 即可。

思路:
如果直接分别对2~N分解质因数，再将结果合成，那么时间复杂度过高会超时。显然N！的质因数不会超过N，那么先求出不超过N的所有素数p，再分别求出其在N！中的次数。对每一个素数p，其在N！中的次数等于在1~N中的次数之和。1~N中能被p整除的有⌊N/p⌋个数，能被p^2整除的有⌊N/p^2⌋个数（也就是说此时p的次数至少有⌊N/p⌋+⌊N/p^2⌋,其中⌊N/p^2⌋不必乘以2，因为被p^2整除的数也被p整除，而此前已经统计过一次p），以此类推，p的次数就有⌊N/p⌋+⌊N/p^2⌋+⌊N/p^3⌋+……+⌊N/p^⌊log(N)/log(p)⌋⌋. 每如此计算一次，时间复杂度为O(logN)，则总复杂度为O(NlogN).

代码：

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

using namespace std;
#define MAX_N 1000005

int v[MAX_N];
int prime[MAX_N];
int c[MAX_N];

int m;
void primes(int n) {
  m = 0;
  memset(v, 0, sizeof(v));
  memset(prime, 0, sizeof(prime));
  for (int i = 2; i <= n; i++) {
    if (v[i] == 0) {
      v[i] = i;
      prime[++m] = i;
    }
    for (int j = 1; j <= m; j++) {
      if (prime[j] > v[i] || prime[j] > n / i) {
        break;
      }
      v[i * prime[j]] = prime[j];
    }
  }
}

int main() {
  int n;
  cin >> n;
  primes(n);
  for (int i = 1; i <= m; i++) {
    long long p = prime[i]; //最后一次极限情况相乘可能溢出所以用ll，有点坑，找了好久
    int t = 0;
    while (n/p) {
      t += n / p;
      p *= prime[i];
    }
    c[i] = t;
  }
  for (int i = 1; i <= m; i++) {
    printf("%d %d\n", prime[i], c[i]);
  }

  return 0;
}

题目链接：POJ-2689

大致题意：给出 L,U (1<=L<U<=2147483647，U-L<=10^6)，找出区间[L，U]中相邻两个质数的差最大是多少，最小是多少。

思路：关键是求出[L,U]内的所有质数，然后一趟比较即可得出结果。线性筛法和Eratosthenes筛法都可求出1~N内的所有质数，而这里U值上界可达2^31，所以即使用线筛也会超时（限制1s，大约是10^7次计算）。但注意到U-L只有10^6，考虑到每个合数都存在一个不超过n^0.5的质因子，我们求出[2,U^0.5]内的所有质数，对其中每个质数p，把[L，U]内能被p整除的数剔除，剩下的就是[L，U]的质数了。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
#include<vector>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define MAX_N 1000005

int prime1[MAX_N];
ll prime2[MAX_N];
int m;
int v[MAX_N];

void primes(int n) {
    memset(v,0,sizeof(v));
    memset(prime1,0,sizeof(prime1));
    m=0;
    for(int i=2; i<=n; i++) {
        if(v[i]==0) {
            v[i]=i;
            prime1[++m]=i;
        }
        for(int j=1; j<=m; j++) {
            if(v[i]<prime1[j]||i>n/prime1[j]) {
                break;
            }
            v[i*prime1[j]]=prime1[j];
        }
    }
}

int main() {
    ll L, U;
    primes(sqrt(2147483647)); //预处理
    while(cin>>L>>U) {
        memset(v,0,sizeof(v));
        memset(prime2,0,sizeof(prime2));
        int n=0;
        for(int i=1; i<=m; i++) {
            if(prime1[i]>sqrt(U)) break;
            for(ll j=L/prime1[i]; j<=U/prime1[i]; j++) {
                if(prime1[i]*j>=L&&j>1) //要注意的地方
                    v[prime1[i]*j-L]=1;
            }
        }
        if(L==1) v[1-L]=1; //要注意的地方
        for(ll i=L; i<=U; i++) {
            if(!v[i-L]) {
                prime2[++n]=i;
            }
        }

        ll maxn=0;
        ll minn=2147483647;
        ll a,b,c,d;
        for(int i=1; i<=n-1; i++) {
            if(maxn<prime2[i+1]-prime2[i]) {
                maxn=prime2[i+1]-prime2[i];
                a=prime2[i];
                b=prime2[i+1];
            }
            if(minn>prime2[i+1]-prime2[i]) {
                minn=prime2[i+1]-prime2[i];
                c=prime2[i];
                d=prime2[i+1];
            }
        }
        if(n<2)
            printf("There are no adjacent primes.\n");
        else
            printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",c,d,a,b);
    }
    return 0;
}