P14074 [GESP202509 五级] 有趣的数字和

题目背景

对应的选择、判断题：https://ti.luogu.com.cn/problemset/1193

为保证只有时间复杂度合理的算法通过本题，本题时限下调。

题目描述

如果一个正整数的二进制表示包含奇数个 1，那么小 A 就会认为这个正整数是有趣的。

例如，7 的二进制表示为 (111)2​，包含 1 的个数为 3 个，所以 7 是有趣的。但是 9=(1001)2​ 包含 2 个 1，所以 9 不是有趣的。

给定正整数 l,r，请你统计满足 l≤n≤r 的有趣的整数 n 之和。

输入格式

一行，两个正整数 l,r，表示给定的正整数。

输出格式

一行，一个正整数，表示 l,r 之间有趣的整数之和。

输入样例

3 8

输出样例

19

输入样例2

65 36248

输入样例2

328505490

这题我将分不同的方法写

1：辗转相除法

AC代码1

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
if(b==0) return a;
return gcd(b,a%b);
}
int main(){
int n,a,ans=1;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a;
ans*=a/gcd(ans,a);
}
cout<<ans;
return 0;
}

AC代码2

#include <bits/stdc++.h>
using namespace std;
int n,a[20],s=1,x;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>x;
s*=x/__gcd(s,x);
}
cout<<s;
return 0;
}

方法2：正常思路，暴力！！！（压缩时间复杂度，压缩到1.00s)

AC代码

#include<bits/stdc++.h>
using namespace std;
int n,a[105],c;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
int m = unique(a+1,a+n+1) – (a+1);//去重 函数 也可以用for循环一一遍历
for(int i=a[n];;i+=a[n]){//每次加上最大的数
int f=0;
for(int j=m;j>=1;j–){ //从大到小遍历，节省时间复杂度
if(i%a[j]!=0){ //例如输入 [2, 3, 4]
f=1;//每次只需递增最大数 检查 4,8,12
break;
}
}
if(!f){
cout<<i;
return 0;
}
}
return 0;
}

本题的主题思想还是辗转相除法，如果考级时用暴力的话，会浪费诸多时间用来排找代码，优化时间复杂度。