���
\(\Huge打了一场模拟赛，又垫底了。qwq\)
2024初三年前集训测试2
T1上海
\(0pts\)
死因
- \(__int128\) 不支持 \(pow\) 。
- 事实上我打了一个快速幂
（在一千行代码里翻出来就行）。但是我打 \(qpow\) 时忘打 \(q\) 了，然后本地运行还没报错……就交上去了 - 之后结果就是，没过编。。。
- 改成
龙龙就对了。
题解
- 还是比较好打的，给一个正整数 \(k(1\leq k\leq 10^{12})\) ，判断是否有一个正整数 \(n\) 使得 \(n^2\) 为 \(k\) 的倍数且 \(n\) 不是 \(k\) 的倍数。
- 想到对其进行分解质因数，一个数的平方质因子次数都是偶数，也就是说，假如 \(k\) 的质因子次数都为 \(1\) 那么就是无解的。
- 而有解情况就是 \(k\) 有次数大于 \(1\) 的质因子 （不是 \(square~free~number\) ）。解就是 \(\LARGE\sum\limits_{i=1}^np_i^{\lceil\large\dfrac{c_i}{2}\rceil}\) 。
- 因此记录质因子以及次数，之后处理一下即可。
代码
说的再多也不如代码好使。
#include<bits/stdc++.h>
#define int __int128//long long就够了
#define N (1000010)
#define sort stable_sort
using namespace std;
namespace IO
{
#define ll __int128
const int MAX=1<<24;
char buf[MAX],*p1=buf,*p2=buf;
char obuf[MAX],*o=obuf;
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<24,stdin),p1==p2)?EOF:*p1++)
//template<typename T>
//inline T read()
inline int read()
{
int x=0;bool f=1;
char c=gc();
for(;c<48||c>57;c=gc())if(c=='-')f=0;
for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
return f?x:~x+1;
}
void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
void write(ll x,char end){pit(x);*o++=end;}
void flush(){fwrite(obuf,o-obuf,1,stdout);}
#undef ll
}
using IO::read;using IO::write;using IO::flush;using std::complex;
inline int min(int x,int y){return y&((y-x)>>31)|x&(~(y-x)>>31);}
inline int max(int x,int y){return x&((y-x)>>31)|y&(~(y-x)>>31);}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
long long n,m;
int qpow(int x,int b)
{
int ans=1;
for(;b;b>>=1){if(b&1)ans=(ans*x);x=(x*x);}
return ans;
}
int pr[100],cnt[100],tot,ans=1;
signed main()
{
init_set();
n=read();
int len(sqrt(n)),nn(n);
for(int i(2);i<=len;++i)
{
if(!(nn%i))pr[++tot]=i,++cnt[tot],nn/=i;
for(;!(nn%i);nn/=i)++cnt[tot];
}
if(nn>1)pr[++tot]=nn,++cnt[tot];
for(int i(1);i<=tot;++i)
{
if(cnt[i]!=1)break;
if(i==tot)puts("-1"),exit(0);
}
for(int i(1);i<=tot;++i)
ans*=pow(pr[i],((cnt[i]+1)>>1));
write(ans,' ');
flush();
return 0;
}
T2华二
\(0pts\)
话说为啥这次模拟赛题目名字这么瞩目。- 一个 \(1\leq a_i\leq 9\) 的数列，当 \(\gcd(a_i,a_{i+1})=1\) 时，就可以把它们的位置交换。
- 显然，对于 \(1\) \(5\) \(7\) 这三个法外狂徒来说，它们可以随意地变换位置。
- 对于 \((2,3)\) \((2,7)\) \((2,9)\) \((3,4)\) \((4,9)\) \((8,9)\) 六对数来说，也是可以交换的。
- 并且我们发现，可以将 \(6\) 单独分出来，因为它不能与其他数交换（ \(1\) ， \(5\) ， \(7\) ）除外