蒟蒻勉强打了3题，第4题开始不会了。。
这里放了前4题的代码和题解。

  • A 小G的sum

    显然对于任意一个数i，最大的约数为i，最小的约数为1.
    因此答案就是n+(1+2+3...n)=n+(1+n)*n/2
    注意开long long

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n;
    cin>>n;
    long long ans;
    ans=n+(1+n)*n/2;
    cout<<ans<<endl;
}

  • B 小G的GCD

    根据f(x)的定义我们可以知道，f(x)=(1+2+3+...int(x/k))*k
    因此我们枚举f(i)求和就可以了。
    代码：

    #include<bits/stdc++.h>
using namespace std;
int n,k;
long long solve(int x){
 // if(x<k)return 0;
  int t=x/k;
  return 1ll*(1+t)*t/2*k;
}
int main()
{
  long long ans=0;
  cin>>n>>k;
  for(int i=1;i<=n;i++){
      ans+=solve(i);
  }
  cout<<ans<<endl;
  return 0;
}

  • C 小G的约数

    首先G(n)我们可以暴力计算，然后发现要算G(G(n))的话，会超时的。
    再回过来看f(n)的定义是f(n)=n的约数和。
    G(n)=f(1)+f(2)+...f(n)
    可以发现G(n)其实的是n个1+n/2个2+n/3个3+...n/n个n
    即G(n)=n1+int(n/2)2+int(n/3)3+...int(n/i)i+...int(n/n)*n
    可以发现这其实是一个整除分块，对于k=int(n/i)我们可以分出其中的一个连续块，令区间[l,r]中的任意一个i，使得int(n/l)=int(n/r)=int(n/i)。
    而这个r=n/(n/l)
    这里的复杂度为O(logn)
    那么我们直接计算出G（n）以后，再利用整除分块计算G(G(n))就可以了。
    代码：

    #include<bits/stdc++.h>
using namespace std;
int n;
long long g;
int main()
{
  cin>>n;
  for(int i=1;i<=n;i++){
      g+=n/i*i;
  }
  long long ans=0;
  for(long long l=1,r;l<=g;l=r+1){
      r=g/(g/l);
      ans+=(g/l)*(l+r)*(r-l+1)/2;
  }
  cout<<ans<<endl;
  return 0;
}

事实上，在做本题之前我只做过一题整除分块，对这玩意也是一知半解。我在比赛中，想到的是上面的那个式子可以转化成n*n-(n%1+n%2+n%3+...n%n)
因此我们只要求后面的那个式子就好了。
首先可以发现对于i>n/2的情况，是一个等差数列。即在(n/2,n]区间内是等差数列，公差为1。
同理可以发现，(n/3,n/2]是公差为2的等差数列。
因此我们可以枚举这些区间，到什么时候结束呢？
我们可以计算从以n/sqrt(n)开始的区间，到最后的(n/2,n]的区间利用等差数列公式求和，sqrt(n)之前的我们可以暴力计算。

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
long long g;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        g+=n/i*i;
    }
    long long ans=g*g;
    int t=sqrt(g);
    for(int i=1;i<=g/t;i++){
        ans=ans-g%i;
    }
    for(int i=2;i<=t;i++){
        long long len=g/(i-1)-g/i;
        ans=ans-(g%(g/(i-1))+g%(g/i+1))*len/2;
    }
    cout<<ans<<endl;
    return 0;
}

  • D 小G的LY数对

    这题暴力也没想到。。
    看了一下别人的题解，也是利用暴力+哈希过的。
    之前没有用过unorder_map
    基本思路就是先把a数组里的数放到unorder_map中，然后暴力枚举b数组中的数并且枚举(i,j)两个位置修改b数组的数，修改完以后看一下map中这个数字有多少个放到答案里面进行统计。
    这样做估计的复杂度是O(30^2*n)，加上map的巨大常数，直接T了。
    参考了一下，有人用bitset先判数字是否在a中出现，然后再去看有多少个答案进行统计。
    算是卡过去了。
    先把代码贴一下，明天有时间写一下哈希的代码：
    #include<bits/stdc++.h>
using namespace std;
int n,m,b[300040],c[30];
unordered_map<int,int>mp;
bitset< 1<<30 >v;
inline int read(){
  int s = 0, w = 1; char ch = getchar();
  while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
  while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
  return s * w;
}
int main()
{
  mp.reserve(300005);
  n=read();m=read();
  int i,j,k,x;
  for(i=1;i<=n;i++){
      x=read();
      v[x]=true;
      mp[x]++;
  }
  for(i=1;i<=m;i++){
      b[i]=read();
  }
  long long ans=0;
  int tmp;
  for(i=0;i<30;i++){
      for(j=i+1;j<30;j++){
          for(k=1;k<=m;k++){
              tmp=b[k];
              tmp^=(1<<i);
              tmp^=(1<<j);
             if(v[tmp]) ans+=mp[tmp];
          }
      }
  }
  cout<<ans<<endl;
  return 0;
}

今天把哈希表的代码补上。速度快很多

#include<bits/stdc++.h>
using namespace std;
const int mod=1000007;
int n,m,b[300040];
inline int read(){
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
struct node{
    int to,next,w;
}p[300050];
int tot,head[2000050];
void add(int x){
    int a=x%mod;
    for(int i=head[a];~i;i=p[i].next){
        if(p[i].to==x){
            p[i].w++;
            return;
        }
    }
    p[tot].to=x;p[tot].w++;p[tot].next=head[a];head[a]=tot++;
}
int query(int x){
    int a=x%mod;
    for(int i=head[a];~i;i=p[i].next){
        if(p[i].to==x){

            return p[i].w;
        }
    }
    return 0;
}
int main()
{
    memset(head,-1,sizeof(head));
    n=read();m=read();
    int i,j,k,x;
    for(i=1;i<=n;i++){
        x=read();
        add(x);
    }
    for(i=1;i<=m;i++){
        b[i]=read();
    }
    long long ans=0;
    for(int i=0;i<30;i++){
        for(int j=i+1;j<30;j++){
            for(int k=1;k<=m;k++){
                int tmp=b[k];
                tmp^=(1<<i);
                tmp^=(1<<j);
                ans+=query(tmp);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}