题目目录: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); } }