G.双生
质数筛 #欧拉筛 #数学
题目
思路
要使\(xyz\)不是完全平方数，设\(a=xyz=p_{1}^{q_{1}}p_{2}^{q_{2}}\dots p_{k}^{q_{k}}\)，则有\(\left( \sum_{i=1}^kq_{i} \right)\%2=1\)
为了方便计算，设\(f(a)=\sum_{i=1}^kq_{i}\)，即让\(f(a)\%2=1\)
注意到\(f(xy)=f(x)+f(y)\)，则\(f(a)=f(xyz)=f(x)+f(y)+f(z)\)
若存在\(f(x)\)为偶，则可选取\(f(y),f(z)\)同为奇或同为偶使得\(f(xyz)=0\)，舍去
若不存在\(f(x)\)为偶，即\(f(x)\)为奇，那么\(f(y),f(z)\)必然也为奇，\(f(xyz)=1\)恒成立
因此题目便转换为了求\(\frac{n}{2}\)个\(f(x)\%2=1\)的数\(x\)，用欧拉筛\(o(n)\)预处理即可
代码实现
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<numeric>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = (a); i <= (b); i ++)
#define per(i, a, b) for(ll i = (a); i >= (b); i --)
#define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n';
constexpr ll inf = 1e9 + 5;
// #define int ll
constexpr ll mod=998244353;vector<ll>prime,vis;
vector<bool>cnt;
void sieve(ll len) {vis.assign(len + 1, 0);prime.reserve(len+1);cnt.resize(len+1,0);prime.push_back(0);rep(i, 2, len) {if (!vis[i])prime.push_back(i);for (ll j = 1; i * prime[j] <= len&&j<prime.size(); j++) {vis[prime[j] * i] = 1;if (i % prime[j] == 0)break;}}rep(i,2,len){int cnt0=0,now=i;for(int j=1;prime[j]*prime[j]<=now;j++){while(now&&now%prime[j]==0)cnt0++,now/=prime[j];}if(now!=1)cnt0++;if(cnt0&1)cnt[i]=1;}
}void eachT() {int n;cin>>n;vector<int>ans;ans.reserve(n/2);rep(i,1,n)if((ans.size()<n/2)&&cnt[i])ans.push_back(i);see(ans);
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);ll t = 1;sieve(1e6+5);cin >> t;while (t--) { eachT(); }
}
J.象牙
gcd #数学
题目
思路
看见本题的第一个思路便是想利用式子：
由于\(gcd(a^b,c^d)\)的幂次不尽相同，所以尝试主动构造相同的进行分布计算：
接下来便思考如何将\(gcd\)中的乘法分解开：
这实际上可以用容斥来理解，要求\(a\times b\)与\(c\)的公共部分，那么就等于\(a\)与\(c\)的公共部分再加上\(b\)与\(c\)的公共部分，再减去\(a,b,c\)的公共部分
因此带入上式：
观察第二项\(gcd\)，又是一个形如\(gcd(a^b,c^d)\)的算式，因此可以通过递归求解
当\(gcd(a,c)=1\)时，原式退化为\(gcd(a^{b-d},c^d)\)，由\(gcd\)的交换性质，实际上这个式子可以一直使\(gcd\)中两个数的幂次不断减小，最终必然变为\(gcd(a,c)\)，答案即为1
因此\(gcd(a,c)=1\)即为终止条件
ps：本题卡常非常严重，赛时用函数递归一直在\(TLE\)，最终使用了\(constexpr\)加速以及迭代写法才最终过了...
代码实现
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<numeric>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(ll i = (a); i <= (b); i ++)
#define per(i, a, b) for(ll i = (a); i >= (b); i --)
#define see(stl) for(auto&ele:stl)cout<<ele<<" "; cout<<'\n';
constexpr ll inf = 1e9 + 5;
// #define int ll
constexpr ll mod=998244353;
constexpr ll qpow(ll a,ll b){ll ans=1;a%=mod;while(b>0){if(b%2){ans*=a;ans%=mod;}a*=a;a%=mod;b>>=1;}return ans%mod;
}void eachT() {ll a,b,c,d;cin>>a>>b>>c>>d;ll ans=1;while(1){if(b==d){ans*=qpow(gcd(a,c),b);ans%=mod;break;}if(b>d){ll G=gcd(a,c);if(G==1)break;ans*=qpow(G,d);ans%=mod;c/=G;b-=d; }else{ll G=gcd(a,c);if(G==1)break;ans*=qpow(G,b);ans%=mod;a/=G;d-=b; } }cout<<ans<<'\n';
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);ll t = 1;cin >> t;while (t--) { eachT(); }
}