Mod, Or and Everything
题目大意：给出一个数n，我们要求从1到n的异或和，最后输出结果。
多组测试? 数据范围为1~1e12.
思路：打表，找到规律，发现结果都是(2^k)-1,输入n，通过查找得到对应的输出值。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int b[100],n;
void init(){
? ? b[0]=1;
? ? for(int i=1;i<=60;i++) b[i]=b[i-1]*2;
}//记录2的60次方?
signed main(){
? ? int T;
? ? cin>>T;
? ? init();
? ? while(T--){
? ? ? ? cin>>n;
? ? ? ? int x=lower_bound(b,b+60,(n+1)/2)-b; //找到下标
? ? ? ? cout<<b[x]-1<<endl;
? ? }
? ? return 0;
}?
?
Minimum spanning tree
题目大意：输入一个数字n，节点编号为从2到n的n-1个节点，每条边的权值为左右端点的最小公倍数，求出将所有点走完的最小路径，即最小生成树。
多组测试，数据范围2到1e12.
根据正常思路无论是prim算法还是kruskal算法，这么大的数据肯定会爆掉，因此需要想其他方法。根据题意有，每条边的权值为两个点的最小公倍数，因此，可以想到，对于任何一个大于2的数x，是一个素数的时候，最小边权为2*x，对于一个盒数y来说，最小边权为它本身（一个它的因数和它本身的最小公倍数为它本身），因此将所有节点的最短边加起来输出即可。
代码：
#include <bits/stdc++.h>
using namespace std;
long long prime[900000]={};//存素数?
bool f[10000000]={};//标记素数还是合数?
int p[10000000]={};
int t,n;
int main(){
?? ?//欧拉筛去除合数 2的倍数 3的倍数 。。。。?
? ? for(int i=2;i<=10000000/2;i++){
? ? ? ? int k=2; ? ? ?
? ? ? ? while(k*i<=10000000){
? ? ? ? ? ? f[k*i]=1;
? ? ? ? ? ? k++;
? ? ? ? }
? ? }
? ??
? ? int top=0;
? ? //存入素数?
? ? for(int i=2;i<10000000;i++){
? ? ? ? if(f[i]==0) prime[top++]=i;
? ? }
? ??
? ? cin>>t;
? ? while(t--){
? ? ? ? cin>>n;
? ? ? ? long long ans=0;
? ? ? ? int index=1;
? ? ? ? if(n==2){
? ? ? ? ?? ?//2的时候只有一个顶点为0?
? ? ? ? ? ? cout<<0<<endl;
? ? ? ? ? ? continue;
? ? ? ? }
? ? ? ? while(prime[index]<=n){
? ? ? ? ?? ?//所有在范围内的素数权值为2?
? ? ? ? ? ? ans+=2*prime[index];
? ? ? ? ? ? //做标记?
? ? ? ? ? ? p[prime[index]]++;
? ? ? ? ? ? index++;
? ? ? ? }
? ? ? ? for(int i=3;i<=n;i++){
? ? ? ? ? ? if(p[i]==0)ans+=i; ? ? ? ? ? ?
? ? ? ? }
? ? ? ? cout<<ans<<endl;
? ? }
? ? return 0;?
}
|