题目目录：1005 1001
1001题 Mod, Or and Everything
题目大意：给出一个整数n，计算(n mod 1)或(n mod 2)或...或(n mod (n - 1))或(n mod n)。

思路：将一个数n对所有小于它的数i取模可以发现，当i>n/2时，n%i=n-i，由于偶数/2后得到的是正确的数字，而奇数/2后等于(n-1)/2，所以最大的余数等于(偶数：n/2-1，奇数:(n-1)/2) ，最大的余数的二进制位记为K，最终的答案会等于2^k-1，读者可以拿n=30和n=29模拟过程，也许会更好理解。 

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t,k;
    long long n,m;
    cin>>t;
    while(t--){
        k=0;
        cin>>n;
        if(n%2==0) m=n/2-1;
        else m=(n-1)/2;
        while(m){
            k++;
            m/=2;
        }
        cout<<pow(2,k)-1<<endl;    
    }
    return 0;
}

1005题 Minimum spanning tree
题目大意：给定n-1个点，编号从2到n，两点a和b之间的边权重是lcm(a，b)。请找出它们形成的最小生成树。

思路：对于所有点，编号为质数的向2连边，所有编号为合数的向它的因子连边，这样形成的生成树一定最小。总的边权和为2*质数的和+合数的和。找质数可用欧拉筛。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t;
const maxn=1e7+1;
bool h[maxn]={0};
ll prime[maxn],num=1;
void xs(int n){
    for(int i=2;i<=n;i++){
        if(h[i]==0) prime[num++]=i;
        for(int j=1;j<num&&i*prime[j]<=n;j++){
               h[i*prime[j]]=true;
               if(i%prime[j]==0)break;
        }
    } 
}
int main(){
    ll n;
    xs(10000000);
    scanf("%lld",&t);
    while(t--){
        ll ans=0;
        scanf("%lld",&n);
        for(ll i=3;i<=n;i++){
               if(h[i]==0) ans+=2*i;
              else ans+=i;
           }
        printf("%lld\n",ans);
    }
}