社区讨论
为什么会RE呢
B3716分解质因子 3参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m1jaz163
- 此快照首次捕获于
- 2024/09/26 21:01 去年
- 此快照最后确认于
- 2025/11/04 18:44 4 个月前
CPP
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100;
int m , p[N] ,c[N] , ans = 0;
const int MAX_N = 100;
int v[MAX_N],prime[MAX_N],k;
void Linear_Sieve(int n)//线性筛
{
memset (v,0,sizeof(v));//最小质因子
k = 0;//质数数量
for(int i = 2;i <= n;i++)
{
if(v[i] == 0)//i是质数
{
v[i] = i;
prime[++k] = i;
}
//给当前的数i乘上一个质因子
for(int j = 1;j <= k;j++)
{
//i有比prime[j]更小的质因子,或者超出n的范围
if(prime[j] > v[i] || prime[i] > n/i)
break;
//prime[j]是合数i*prime[j]的最小质因子
v[i * prime[j]] = prime[j];
}
}
}
void Prime_Factorization(int n)//质因数分解
{
m = 0;
Linear_Sieve(n);
for(int i = 1 ; i <= k ; i++)
{
if(n % prime[i] == 0)
{
p[++m] = prime[i] , c[m] = 0;
while(n % prime[i] == 0)
n /= prime[i] , c[m]++;//除掉所有的i
}
}
if(n > 1)
p[++m] = n , c[m] = 1;
for(int i = 1;i <= m;i++)
{
if(c[i] % 2 == 0)
p[i] = 0;
}
for(int i = 1;i <= m;i++)
{
ans ^= p[i];
}
cout << ans << endl;
ans = 0;
}
main()
{
int T;
cin >> T;
for(int i = 1;i <= T;i++)
{
int n;
cin >> n;
Prime_Factorization(n);
}
return 0;
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...