数学问题总结

WanderOvO · 2020-05-06 16:53:38 · 个人记录

数学问题总结

公式化简

• P2671 求和

  题目大意：见原题。

  这个题充分考察了数学式子的化简，以及前缀和的使用，和某逆序对问题的解题关键类似，都是式子化简。本题我还有一些化简感觉不是很自然，先占坑。

位运算相关

• P6306 小玲的书

  题目大意，有n本书，这n本书其实是好几种书，其中保证每种书的本书是k的倍数，现在我往里面再插入一本书，请求出来我插的那本书是哪种书。

  我们知道，k为偶数的时候，就是一道经典的面试题，用到的是异或的思想，即由于插入了一本书，所以肯定有某种书为奇数本了。而两本相同种类的书，异或之后结果是0，所以，把所有书的种类做一个异或，最后得到的数就是新插入的书的种类。

  那么k为奇数的时候呢？这里要介绍一下异或运算的本质：不进位加法。0^0=0 0^1=1 1^0=1 1^1=0，是不是？裸的异或是二进制运算，也就是说，两个一样的做异或运算，得到的是0，那么我们可以思考，能不能发明一种k进制异或运算，使得有k个一样的数进行这个运算时，结果是0呢？如果理解了不进位加法的思想，会发现这是可行的。我们把书的种类变成k进制数，然后把k的倍数本书的种类的k进制表示都做不进位加法（最后统一对k进制位取模）,那么，如果这些书编号都是一样的，那么他们的k进制表示也是一样的，所以它们的每个k进制位加起来之后肯定都是k的倍数（因为是k的倍数本一样的书做不进位加法）,每一位都对k取模之后肯定是0啦。所以，我们对所有的n+1本书都做k进制不进位加法，然后取模，最后把得到k进制数变回10进制，就是插入的书的种类啦。至于复杂度，如果种类最大是A，则复杂度为O(nlog(A))。当然，这个题这样还过不了，因为出题人太毒瘤了，把A设得特别大，所以这道题目正解是把64位数变成4个16位数（2进制），然后对于n+1本书，看看每本书的这4个部分出现了多少次，把不是k的倍数的部分拎出来，最后一整合就是插入的书了。

  不进位加法思路代码如下(75pts)：

  #include <bits/stdc++.h>
  #define ll long long
  using namespace std;
  const int N=1e7+8;
  ll n,k,ans;
  ll tmp[66];
  int main(){
  ll x;
  scanf("%lld %lld",&n,&k);
  if(k%2==0){
      scanf("%lld",&ans);
      for(int i=2;i<=n;i++){
          scanf("%lld",&x);
          ans=ans^x; 
      }
      printf("%lld\n",ans);
  } else {
      for(int i=1;i<=n;i++){
          scanf("%lld",&x);
          for(int j=0;x;j++,x=x/k)
              tmp[j]+=x%k;
      }
      for(int j=0;j<64;j++)
          tmp[j]%=k;
      for(int j=63;j>=0;j--)
          ans=ans*k+tmp[j];
      printf("%lld\n",ans);
  }
  return 0;
  }

  正解代码如下(不需要读入优化)：

  #include <bits/stdc++.h>
  #define ll long long
  #define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,100000,stdin),pa==pb)?EOF:*pa++
  using namespace std;
  ll n,k,ans;
  ll tmp[5][(1<<16)+9];
  static char buf[100000],*pa(buf),*pb(buf);
  inline ll readint();
  int main(){
  ll x;
  n=readint();
  k=readint();
  //    scanf("%lld %lld",&n,&k);
  for(int i=0;i<n;i++){
      x=readint();
  //        scanf("%lld",&x);
      tmp[3][(x>>48)&0xffff]++; //统计每个数的块出现的个数
      tmp[2][(x>>32)&0xffff]++; //统计每个数的块出现的个数
      tmp[1][(x>>16)&0xffff]++; //统计每个数的块出现的个数
      tmp[0][x&0xffff]++; //统计每个数的块出现的个数
  }
  for(ll i=3;i>=0;i--){
      for(ll j=0;j<65536;j++){
          if(tmp[i][j]%k){
              ans|=(j<<(i*16));
              break;
          }
      }
  }
  printf("%lld\n",ans);
  return 0;
  }
  inline ll readint() {
  ll x=0;char c=gc;
  while(c<'0'||c>'9')c=gc;
  for(;c>='0'&&c<='9';c=gc)x=x*10+(c&15);
  return x;
  }

数论

• P1372

  题目大意：从数1-n个中取出k个数，使得这k个数最大公因数最大，求这个最大公因数。

  可能比较容易想到的一个方法是筛法：我可以尝试从大到小枚举这个最大公因数，然后看看能筛去哪些数，第一次枚举到的能够筛去超过k个数的数就是最大公因数了。不过这个题n的规模是1e9，会TLE。这时候我们要换方法，毕竟数论题有些就是结论嘛，说不定有一些结论可以用到。其实有了刚才筛法的经验，或许我们不难想到，要想用筛法筛出来k个数，那么这个最大公约数肯定不能大于[\frac{n}{k}]，不然根本筛不够k个，即gcd<=[\frac{n}{k}]。另一方面，如果我们求出了gcd，那么肯定是筛去了gcd,2gcd...kgcd ，如果gcd=[\frac{n}{k}]，那么显然有kgcd<=n，即gcd=[\frac{n}{k}] 是合法的。所以，要求的最大的gcd就是\frac{n}{k}了。虽然我们不一定能直接想到这个结论，但是，我们还是能够通过筛法去发现这个结论的。

• P3951 小凯的疑惑

  题目大意：对于代数式ax+by，已知a,b 为正整数，由输入给定，且令x,y取遍所有非负数值，并保证这时ax+by不能组合出来的整数c有最大值，求这个最大的c

  朴素的想法是，我们可以发现c的最小可能取值是max(a,b)-1 ，最大应该不会超过ab （我没独立严谨地想出来），所以我们从大到小枚举c（答案没有单调性，只能顺序枚举），每枚举一次，就做一次exgcd来判断一下，先看有没有整数解，再看有没有正整数解，第一个不合理的c 就是答案了。这个思路可以轻易通过60\% 的数据。

  剩下的40\%的数据，a,b很大，原算法会超时。由于我们前面的算法是基于枚举的，所以可能会比较慢，但exgcd这个工具应该还是有必要用的，只不过需要变形一下。根据题意，如果c求出来了，那么令d=c+1，ax+by=d是有合理解的。那么，我们就是想求这样一个最大的d：ax+by=d有合理解，且ax+by=d-1没有合理解(这一步非常重要，是数学中的一种很常见的思路，化归的思想)。如果ax+by=d-1也有合理解，至少有整数解，假设ax_1+by_1=d，那么就有a(x_1-\Delta x)+b(y_1-\Delta y)=d-1 ,化简一下并带入上式有a\Delta x+b\Delta y=1 。要解出来整数\Delta x和\Delta y，需要gcd(a,b)=1。也就是说如果没有gcd(a,b)=1的话，这个题目的数据就有锅，就没法保证有最大的c。假设题目数据没锅，那么能解出来可能的\Delta x和\Delta y 。然后就不会分析了。

  偷偷看了一眼提示，由于gcd(a,b)=1，所以肯定有整数解，我们现在求出两组解，一组是(x',y')，另一组是(x'',y'')，其中，x'是这个方程的整数解中\Delta x非负且最小的，y''是这个方程整数解中\Delta y非负且最小的。 要想让ax+by=d-1没有合理解，需要x_1-\Delta x和y_1-\Delta y中至少有一个恒为负数。如果\Delta x取x',都能让x_1-\Delta x=x_1-x'<0 ，或者\Delta y取y''，都能让y_1-\Delta y=y_1-y''<0 ，二者中至少有一个成立，那就肯定不会有非负整数解了。为了让d尽可能小，我们取x_1=x'-1，y_1=y''-1 ，则a(x'-1)+b(y''-1)就是我们所说的最大的d，d-1就是最大的不能被组合出来的数。就这样，答案就被构造出来了。虽然这个比某个很暴力一个式子就能艹过去的方法要弱，但是，能摆脱大家对于小学奥数的阴影。

  小学奥数做法：如果a,b都至少选一个的话，那么最大的ax+by拼不出来的是ab,怎么来的？大胆猜想，无需证明。那么如果a,b可以不选的时候，只要在ab的基础上减去a+b即可了。严谨的证明这里我不再给出。

  我认为的标准做法代码如下：

  #include <bits/stdc++.h>
  #define ll long long
  using namespace std;
  void exgcd(ll a,ll b,ll c,ll &x,ll &y);
  ll lcm(ll a,ll b);
  ll gcd(ll a,ll b);
  int main(){
  ll a,b,x,y,minx,miny,k,l;
  scanf("%lld %lld",&a,&b);
  k=lcm(a,b)/a;
  l=lcm(a,b)/b;
  exgcd(a,b,1,x,y);
  minx=((x%k)+k)%k;
  miny=((y%l)+l)%l;
  printf("%lld\n",a*(minx-1)+b*(miny-1)-1);
  return 0;
  }
  ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
  }
  ll gcd(ll a,ll b){
  if(b==0){
      return a;
  }
  return gcd(b,a%b);
  }
  void exgcd(ll a,ll b,ll c,ll &x,ll &y){
  if(b==0){
      x=c;
      y=0;
      return;
  }
  exgcd(b,a%b,c,x,y);
  ll tmp=x;
  x=y;
  y=tmp-(a/b)*y;
  return;
  }

• CF762A

  题目大意：找到n的第k小的因子（不一定是素因子），或者告知其不存在。n的规模是1e15，k的规模是1e9

  根据数据范围可以知道，这道题起码要是O(\sqrt n)的算法，或者找规律O(1) 。

  如果n 有第k小的因子的话，那么要么这个因子小于等于\sqrt n，要么大于\sqrt n。我们可以枚举从1到\sqrt n的所有的数，判断是不是因子，如果在这个范围内就找到了，那么皆大欢喜，如果没找到，假如在小于等于\sqrt n的情况下找到了m个因子，如果\sqrt n也是n的因子的话，那么一共就有2m-1个因子。如果2m-1<k，则无解，否则，我们可以根据对称性，首先我们知道第k个因子以及后面的因子一共有2m-1-k+1=2m-k个，即从右往左数，k是第2m-k个数，所以在左边我们直接找第2m-k个，然后被n除就好了。如果\sqrt n不是n的因子，那么一共有2m个因子。如果2m<k，则无解，否则根据对称性，我们要找左边的第2m-k+1个元素，被n除就是结果了。

• CF776B

  题目错误大意：数列2,3,……n+1 ，每个数字都要刷上一种颜色，且如果一个数是另一个数的因子，那么这两个数要刷不同的颜色，且要尽量少用颜色。给定n，求至少要用多少种颜色。

  尝试了一下知道，n=2时需要1种，n=3……6时需要2种，n=7时需要3种。这样来看，似乎和取以2为底的对数有关系。考虑了一下：给定了一个n，然后我们写出来那个序列，现在我们截取序列的第2^i 到第2^{i+1}项。显然，这个区间里面不可能有倍数关系，因为即使是右端点的数，也没法大于左端点的2倍，所以更不可能是其他倍了。而如果是第2^i到第2^{i+1}+1项，那么右端点正好是左端点的2倍，就不能使得整个区间染成同一种颜色了。然后，我也不知道对不对。

  然后我他妈的心态崩了！突然发现题目翻译错了！

  题目正确大意：数列2,3,……n+1 ，每个数字都要刷上一种颜色，且如果一个数是另一个数的质因子，那么这两个数要刷不同的颜色，且要尽量少用颜色。给定n，求至少要用多少种颜色。

  纠正题意之后，因为有质因数，所以可能考虑线性筛。显然，质数全都涂一种颜色是可以的，而合数之间，由于不能有一个合数是另一个合数的质因子，所以合数也可以染相同的颜色。所以，当n<3 时，1种，n>=3时，两种。

• P2303 连续最大公因数求和

  题目大意：求 \sum\limits_{i=1}^n \gcd(i, n) 。

  这道题n的规模是1e9，即使是线性方法都会超时，所以必须考虑根号算法或者推公式。在这里的处理方法是用欧拉函数。我们可以发现，\gcd(n,k)=d<=>\gcd(\frac{n}{d},\frac{k}{d})=1 。假如使得\gcd(n,k)=d 的k 有f(d)个，那么使得\gcd(\frac{n}{d},\frac{k}{d})=1 的k也有f(d) 个，由欧拉函数的定义知，f(d)=\phi(\frac{n}{d}) 。所以可以这样考虑这个题目：枚举gcd，当gcd 取k的时候，如果n\% k=0 ，则说明n有这个因数k，那么求f(\frac{n}{k})，就是求小于等于\frac{n}{d}的且和它互质的数的个数。显然，如果某个数i和\frac{n}{d}互质，那么就说明gcd(n,i)=d，所以k*f(\frac{n}{k}) 就是所有 gcd(n,i)=k 的数贡献的和。顺带地，我们也可以把\frac{n}{k}*f(k)求出来，这样的话，我们只需要枚举gcd到\sqrt n 就好了。

• P2155 莎拉公主的疑惑

  题目大意：在[1,n!]中，求有多少个和m!互质的数，结果对数r取模。多组数据n,m输入。

  题目保证了m<=n ，所以答案组成中有一部分是\phi (m!) ，另一部分是[m!+1,n!] 之间的和m!互素的数，

  并且注意到m!包含了[1,m]中所有的素因子。然后又注意到一件有趣的事情：当m>=2时，m!是偶数，也就是说，[m!+1,n!]中所有的偶数（即一半的数）肯定都不与m!互素，剩下的奇数中，质数一定与m!互素，合数看情况，要是能快速求出一个区间之内所有和某个数互素的数就好了。

  如果考虑欧拉函数单点求值公式的话，只要我们知道所有的小于等于m的素数，知道n! ，那么就可以直接求出来ans=n!*\Pi (1-\frac{1}{p_i}) ，其中p_i取所有小于等于m的素数。下面考虑怎么求出来这个数。显然n!可以直接预处理+取模，1e7之内的素数可以线性筛预处理，p_i的逆元可以线性预处理， \Pi (1-\frac{1}{p_i})=\Pi(\frac{p_i-1}{p_i})在有了逆元之后可以线性预处理。都预处理好了之后，就可以O(1)询问了。

  这道题给我们的启示是：如果知道一个数的素因数分解，那么就容易求出在某个区间内有多少个和它互素的数。

  代码就是线性筛模板+线性求逆元模板+线性求欧拉函数模板：

  #include <bits/stdc++.h>
  #define ll long long
  #define INF 9999999999
  using namespace std;
  const int N=1e7+9;
  ll prime[N],inv[N],power[N],ratio[N],cnt;
  bool isprime[N];
  ll n,m,t,mod;
  void getprime();
  void getpower();
  void getinv();
  void getratio();
  int main(){
  scanf("%lld %lld",&t,&mod);
  getprime();
  getpower();
  getinv();
  getratio();
  //    for(int i=1;i<50;i++){
  //        printf("%lld %lld %lld %lld\n",prime[i],power[i],inv[i],ratio[i]);
  //    }
  while(t--){
      scanf("%lld %lld",&n,&m);
      printf("%lld\n",(power[n]*ratio[m])%mod);
  }
  return 0;
  }
  inline void getratio(){
  ratio[1]=1;
  for(ll i=2;i<N;i++){
      if(isprime[i]){
          ratio[i]=(ratio[i-1]*(((i-1)*inv[i])%mod))%mod;
      } else {
          ratio[i]=ratio[i-1];
      }
  }
  }
  inline void getinv(){
  inv[1]=1;
  for(ll i=2;i<N;i++){
      inv[i]=((mod-mod/i)*inv[mod%i])%mod;
  }
  }
  inline void getpower(){
  power[1]=1;
  for(ll i=2;i<N;i++){
      power[i]=(power[i-1]*i)%mod;
  }
  }
  inline void getprime(){
  for(ll i=2;i<N;i++){
      isprime[i]=true;
  }
  for(ll i=2;i<N;i++){
      if(isprime[i]){
          prime[++cnt]=i;
      }
      for(ll j=1;j<=cnt && i*prime[j]<N;j++){
          isprime[i*prime[j]]=false;
          if(i%prime[j]==0){
              break;
          }
      }
  } 
  }

• P4139 上帝与集合的正确用法

  题目大意：见原题。

  在做这道题之前，先说一下几个定理的应用。

  费马小定理：若p为素数，则a^p\equiv a(mod\ p)，进一步，若\gcd(a,p)=1，则a^{p-1}\equiv 1(mod\ p) 。

  欧拉定理：若\gcd(a,n)=1，则a^{\phi(n)}\equiv 1(mod\ n) 。

  这两个定理都可以用来求a相对于一个模数的逆元，如果用费马小定理，则需要模数为素数；如果用欧拉定理，则需要模数与a互素。使用时，转化为快速幂计算即可。

  另一个应用是，遇到求a^b\ mod\ n的时候，如果满足\gcd(a,n)=1，则可以知道a^{\phi(n)}\equiv 1(mod\ n) ，在已知这个的前提下，我们可以缩小b的范围，即让b=b\ mod\ \phi(n) ，然后就容易计算了。

  本题是求2^{2^{2{…}}}\ mod\ p，指数大得不可想象，所以可能考虑用定理把指数控制一下，以求出值。每组询问会给出p ，但是不保证p 为质数。如果给出的p 能满足\gcd(2,p)=1，则可以考虑用欧拉定理，变成求2^{2^{2^{…}}mod\ \phi(p)}\ mod\ p ，这样对指数继续递归，最终\phi(p)一定会变成\phi(2)=1，这个时候，显然2^{2^{2^{…}}}\ mod\ 1=0 ,在这时候就可以回溯了。但是并不是每次递归都能够让\gcd(2,p)=1 的，所以我们要考虑一个更一般的欧拉定理：

  若b>=\phi(m)，则a^b\equiv a^{b\%φ(m)+φ(m)}(mod\ m) 。

  并且原问题转化一下，就是求2^x\equiv x\ (mod\ m)。这道题也让我回忆了递归的易于理解的方法。

• P2568 GCD

  题目大意：求区间[1,n]内所有的无序数对(x,y)的个数。其中(x,y)满足\gcd(x,y)为素数。n=1e7

  有了前面几道题的经验，我们不难发现这道题的答案就是\sum\limits _{i=1}^{n}\ \ \sum\limits _{k|i\ and\ k\ is \ prime}{\phi(\frac{i}{k})} 。不过可惜的是，这个没法像P2303一样利用对称性减少循环次数。

  看了题解，发现此题又是另一种想法：考虑枚举素数，把题目转化为求区间[1,\frac{n}{p}]内所有的\gcd(x',y')=1的无序数对的个数，其中x=x'p,y=y'p。这样的话O(n)枚举p，然后依托前缀和，O(1) 计算有多少对最大数是\frac{n}{p}的这样的数对。关于前缀和的处理，我们要线性求出欧拉函数的前缀和，需要基于线性筛，由于每个合数都是被它最小的素因子筛去的，所以可以利用欧拉函数的两个递推公式去做，即若\gcd(p,a)=1，则\phi(pa)=(p-1)\phi(a)，否则，\phi(pa)=p\phi(a)。这样就好了。

  如果是有序数对呢？除了x=y的情况，我们都要加倍。所以，对于每个前缀和，我们乘2减1就好了。

  代码如下，主要是依靠线性筛线性预处理欧拉函数：

  #include <bits/stdc++.h>
  #define ll long long
  #define INF 999999999999
  using namespace std;
  const int N=1e7+9;
  ll n,sum[N],euler[N],prime[N],cnt,ans;
  bool isprime[N];
  void pre();
  int main(){
  scanf("%lld",&n);
  pre();
  for(ll i=0;i<cnt;i++){
      ans=ans+2*sum[n/prime[i]]-1;
  }
  printf("%lld\n",ans);
  return 0;
  }
  void pre(){
  for(ll i=2;i<=n;i++){
      isprime[i]=true;
  }
  euler[1]=1;
  for(ll i=2;i<=n;i++){
      if(isprime[i]){
          prime[cnt++]=i;
          euler[i]=i-1;
      }
      for(ll j=0;j<cnt && i*prime[j]<=n;j++){
          isprime[i*prime[j]]=false;
          if(i%prime[j]==0){
              euler[i*prime[j]]=(prime[j])*euler[i];
              break;
          } else {
              euler[i*prime[j]]=(prime[j]-1)*euler[i];
          }
      }
  }
  for(ll i=1;i<=n;i++){
      sum[i]=sum[i-1]+euler[i];
  }
  }

• CF632D

  未完待续

  题目大意：有一个数列，取出一个最长的符合要求的子列，输出子列长度以及这个子列的元素。这个子列要满足的条件是：里面所有元素的最小公倍数不超过m。

  之前有一道类似的题目是：有一个集合，希望从中取出一些数，使得它们的最大公约数不是1，且取出的数尽可能多，求最多能取出来多少个数。那个题目的做法是枚举gcd，看看每次能选出来多少个数，这里是用了桶进行了优化，能够迅速知道筛掉了哪些数。

• P6583 回首过去

  未完待续

  题目大意：对于x,y\in[1,n]，求有多少对这样的有序对(x,y)，使得\frac{x}{y}能写成有限小数。

  这道题有三档部分分，n的规模一个是1e3，一个是1e7，一个是1e12。

  这里首先要知道一件事情：之所以一个分数\frac{x}{y}能够化成有限小数，是因为能够在保证分子为整数的情况下把化成10^k的形式，也就是说，化成最简分数之后，只有当x=y或者y只有素因子2,5时才能将分数转化为有限小数。

  这样的话，朴素的想法是枚举x,y，然后利用\gcd化成最简，再进行素因数分解，复杂度O(n^2log_2n) ，预计得分40pts。

  由于分数化到最简之后分母只可能含有2,5这两种素因子，所以我们可以考虑先基于优先队列从小到大生成所有的y，其中y<=n且y只可能含有2,5这两种素因子，显然，如果这些y作为分母，那么分子是多少都可以化为有限小数。这样的话，我们似乎可以基于最简分数，生成那些不是最简的分数。

• P2257 YY的gcd

  题目大意：给定 N, M，求 1 \leq x \leq N ,1 \leq y \leq M 且 \gcd(x, y) 为质数的 (x, y) 有多少对。

  是不是贼熟悉？那就对了，前面有道题和这个描述差不多。显然，这道题的答案是ans=\sum\limits_{p\ \in\ prime}\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=p] 。如果暴力计算的话，复杂度是O(tn^3logn) ，对于1e7的数据量以及1e4次询问是完全不可以接受的，属于无脑暴力，我甚至不确定这种做法能拿到分数。这个时候，我们要使用莫比乌斯反演简化计算。同时，这也是我第一次做莫比乌斯反演的题目。

  为了使用莫比乌斯反演，我们需要先构造两个数论函数。题解说有一个套路是：设f(d)为\gcd(i,j)=d的数对(i,j)的个数，则显然f(d)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=d] 。要计算f(d)，我们需要二重循环，实在太慢，我们想优化。考虑到我们想用莫比乌斯反演，所以我们必须再构造一个函数，要么新函数求和等于f(n)，要么f(d)求和得到新函数。在这里，我们使用了倍数的莫比乌斯反演公式，设F(d)表示\gcd(i,j)=kd,k\in\Z^+的数对(i,j)的个数，则F(d)=\sum\limits_{d|k\ and\ k\leq\ min(m,n)}{f(k)} 。根据乘法原理，可以计算出F(d)=[\frac{n}{d}][\frac{m}{d}] 。由莫比乌斯反演，知f(d)=\sum\limits_{d|k}\mu(\frac{k}{d})F(k) ，把F(k)带入就有f(d)=\sum\limits_{d|k}\mu(\frac{k}{d})[\frac{n}{k}][\frac{m}{k}] 。所以， ans=\sum\limits_{p\ \in\ prime}\sum\limits_{p|k}\mu(\frac{k}{p})[\frac{n}{k}][\frac{m}{k}] 。如果计算这个式子，那么复杂度就是O(tnlnn) ，比刚才好了不少，但还是太慢，能够拿到30pts，属于高级暴力。

  在继续优化之前，我认为我们值得思考为什么通过莫比乌斯反演能够降低复杂度。我们本来是要计算f(n)的，但是利用莫比乌斯反演，我们利用F(n)就能表示出f(n)，而F(n) 的计算甚为简单，只需要O(1)的时间就好了，所以相对于裸的暴力优化了O(n^2)的复杂度。

  接下来继续考虑优化。对于 ans=\sum\limits_{p\ \in\ prime}\sum\limits_{p|k}\mu(\frac{k}{p})F(k)，先换一下元，得到ans=\sum\limits_{p\ \in\ prime}\sum\limits_{k=1}^{\frac{min(m,n)}{p}}\mu(k)F(kp) ，再还原，把kp换成T，则ans=\sum\limits_{p\ \in\ prime}\sum\limits_{p|T}^{min(n,m)}\mu(\frac{T}{p})F(T) ，注意到这个式子里面F函数计算时只需要考虑T的取值，所以考虑改变枚举顺序，先枚举T再枚举p，这样做的好处是能把\mu单独放在后面，而\mu函数是积性函数，有良好的性质，可以简化计算。在改变枚举顺序之后，ans=\sum\limits_{T=1}^{min(n,m)}F(T)\sum\limits_{p\ \in\ prime\ and\ p|T}\mu(\frac{T}{p}) 。 对于内层求和，基于线性筛的思想可以预处理出来，即设g(T)=\sum\limits_{p\ \in\ prime\ and\ p|T}\mu(\frac{T}{p})，预处理出g函数的值，这就是\mu函数的妙处。这样的话，复杂度将降为O(tn)。但是由于是多组数据访问，所以还是过不了。本做法能够拿到60pts的好成绩了，属于高级暴力。

  如果想继续优化，我们就不能老老实实地枚举。注意到F(T)=[\frac{n}{T}][\frac{m}{T}] ，可以整除分块，所以，我们对g函数再求一次前缀和，就可以和F函数一起利用分块了，这样复杂度O(t\sqrt n)

  代码如下：

  #include<bits/stdc++.h>
  #define ll long long 
  using namespace std;
  const int N=1e7+9;
  const int M=1e7+9;
  ll prime[N],cnt,t,n,m,mobius[N],ans,maxk,f[N],sum[N];
  bool isprime[N];
  void getprime();
  int main(){
  scanf("%lld",&t);
  getprime();
  while(t--){
      ans=0;
      scanf("%lld %lld",&n,&m);
      maxk=min(n,m); //
  //        for(ll i=0;i<cnt;i++){
  //            for(ll j=1;j*prime[i]<=maxk;j++){
  //                ans+=mobius[j]*(n/(j*prime[i]))*(m/(j*prime[i]));
  //            }
  //        }
  //        printf("%lld\n",ans); //30pts
  //        for(ll i=1;i<=maxk;i++){
  //            ans+=(n/i)*(m/i)*f[i];
  //        } //60pts
      ll l,r;
      for(l=1;l<=maxk;l=r+1){
          r=min(n/(n/l),(m/(m/l)));
          ans+=(n/l)*(m/l)*(sum[r]-sum[l-1]);
      } //100pts
      printf("%lld\n",ans);
  }
  return 0;
  } 
  void getprime(){
  mobius[1]=1;
  for(ll i=2;i<N;i++){
      isprime[i]=true;
  }
  for(ll i=2;i<N;i++){
      if(isprime[i]){
          prime[cnt++]=i;
          mobius[i]=-1;
      }
      for(ll j=0;j<cnt && prime[j]*i<N;j++){
          isprime[i*prime[j]]=false;
          mobius[i*prime[j]]=-mobius[i];
          if(i%prime[j]==0){ //某个素因子次数>1 
              mobius[i*prime[j]]=0;
              break;
          }
      }
  }
  for(ll i=0;i<cnt;i++){
      for(ll j=1;j*prime[i]<N;j++){
          f[j*prime[i]]+=mobius[j];
      }
  }
  for(ll i=1;i<N;i++){
      sum[i]=sum[i-1]+f[i];
  }
  }

  这个题目给我们的启示有：

  1. 使用莫比乌斯反演能简化和gcd有关的统计和计算问题，其原理是用一个计算量小的函数去表示计算量大的函数
  2. 使用莫比乌斯反演时，需要合理地设函数，一种设函数的套路是设f(d)为\gcd(i,j)=d 的数对的个数，然后用约数或者倍数的莫比乌斯去构造另一个函数。
  4. 改变求和顺序看似毫无作用，其实可能能够把一些计算式从内层循环拿出到外层循环，这样有利于各自处理各自的和。
  5. 整除分块是个好东西。

线性代数

• 三根柱子的汉诺塔，只能相邻柱移动，有n个盘子，求移动步数。

  n个盘子要想移动完，需要先把n-1个盘子从第一根柱子移到第三个柱子，然后把第n个盘子移到第二个柱子，再把n-1个盘子移到第一个柱子，再把第n个盘子移到第三个柱子，再把n-1个盘子移到第三个柱子，所以，f[n]=3f[n-1]+2 。这个题n的规模是1e9，所以要加速转移过程。两个方式：一是求出通项公式，然后快速幂，二是利用矩阵快速幂优化dp。