摘要：
A.Odd Set 传送门A.奇数集思考：判断奇偶校验数是否相等。注：（1）特殊情况（2）当余数为时退出，输出No（3）首先判断余数是否为，然后判断代码是否可分割：llt[maxn]，idx；voidsolve（）｛lln=读取，a=读取，b=读取；如果｛ifput；elseputs；return；｝idx=0；对于｛if｛t[i]=1；lltmp=n-t[i]；ifbreak；//cout˂˂t[i-1]˂˂“***”˂˂tmp˂˂endl；if｛put；return；｝｝否则｛t[i]=t[i-1]*a；lltmp=n-t[i]；ifbreak；//cout˂˂t[i-1]˂˂“***”˂˂tmp˂max）的因子，那么，考虑每个数字对答案的贡献，即有多少个数字。因为每个人都会比他少加一次。
思路：
判断奇偶个数是否相等。
代码：
int a[maxn];
void solve(){
int n=read,cnt0=0,cnt1=0;
rep(i,1,2*n){
a[i]=read;
if(a[i]&1) cnt1++;
else cnt0++;
}
if(cnt0==cnt1) puts("Yes");
else puts("No");
}
int main(){
int _=read;
while(_--){
solve();
}
return 0;
}
思路：
首先，当(n)为(a^{x}+y*b)的形式时才在集合里。
只需要枚举(x),判断余数能否整除(b)即可。
注意：
(1.)特判(a==1)的情况
(2.)当余数为(0)时退出，输出No
(3.)先判断余数是否为(0)再判断能否整除(b)
代码：
ll t[maxn],idx;
void solve(){
ll n=read,a=read,b=read;
if(a==1){
if((n-1)%b==0) puts("Yes");
else puts("No");
return ;
}
idx=0;
for(int i=0;;i++){
if(i==0){
t[i]=1;
ll tmp=n-t[i];
if(t[i]>n) break;
//cout<<t[i-1]<<"***"<<tmp<<endl;
if(tmp%b==0){
puts("Yes");return ;
}
}
else{
t[i]=t[i-1]*a;
ll tmp=n-t[i];
if(t[i]>n) break;
//cout<<t[i-1]<<"***"<<tmp<<endl;
if(tmp%b==0){
puts("Yes");return ;
}
}
}
puts("No");
}
int main(){
int _=read;
while(_--){
solve();
}
return 0;
}
思路：
首先，(f(奇数)=2，f(偶数)>=2)
其次，(f(x)<=41)，因为如果(f(x)=y)，那么(lcm(1,2,3,……,y-1))一定是(x)的因子，而(lcm(1,2,3,……,y))一定不是(x)的因子，(lcm(1,2,3,……,41)>max(n)).
然后，考虑每个数对答案的贡献，也就是说(f(x)=y)的数有几个。
由于对于(f(x)>=2)，假设答案最开始为(2*n);
再从(3)开始考虑每个数(y)对答案的贡献，(f(x)>=y)的个数为(n/lcm(1,2,3……y-1))，每次的贡献是(1)。因为每个都会被小于他的加一遍。
代码：
ll n,a[50];
ll gcd(ll a,ll b){
return b==0?a:gcd(b,a%b);
}
ll lcm(ll a,ll b){
return a/gcd(a,b)*b;
}
void init(){
a[1]=1;
for(int i=2;i<=42;i++)
a[i]=lcm(i,a[i-1]);
}
void solve(){
ll n=read;
ll res=2*n%mod;
rep(i,3,41){
res=(res+n/a[i-1])%mod;
}
cout<<res<<endl;
}
int main(){
init();
int _=read;
while(_--){
solve();
}
return 0;
}