社区讨论

为什么会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 条回复,欢迎继续交流。

正在加载回复...