UVA12805题解

A_grasser · 2024-10-01 10:23:11 · 题解

题意简化

给定序列某一项，根据规则判断当前项符号。

解法分析

这题其实就是模拟，所以直接根据它法则判断就行了。

讲一个题目翻译中比较难懂的一块：“如果其所有质因数中，满足由分子为 1，分母为该质因数组成的项前面为减号的质因数个数为奇数，则当前项前面是减号。”

这句话的意思其实是：遍历 n 这一项分母的质因数，判断以该质因数为分母的项的符号是否为减号。最后统计个数，若果是奇数，那么 n 的符号就是减号，反之为加号。

为了使查找质数更快，我们可以先跑一遍线性筛，这样子就能筛出在 10^5 以内的质数了。若不知道什么是线性筛，可先前往此题（线性筛模板）学习。

再讲一个实现技巧：一个质数不是由 n \times 4 + 1 就是由 n \times 4 - 1 组成。这个证明很简单，因为除了 2 以外，其它质数都是单数。而这些数一定可以通过上述一种方法表示，这里不再赘述。

还有一个要注意的是，给 n 做质因数分解时会出现除不尽的情况，要根据 n 再判断一遍符号。

完整代码

//已通过
#include<bits/stdc++.h>
//万能头文件
using namespace std;
bool prime[100009];
int num[100009],cnt;
void init(){//线性筛 
    for(int i=2;i<=100000;i++){
        if(!prime[i]) num[++cnt]=i;
        for(int j=1;j<=cnt;j++){
            if(i*j>100000) break;
            prime[i*j]=1;
            if(i%j==0) break;
        }
    }
}
int main(){
    init();
    int t,n;
    cin>>t;
    while(t--){
        scanf("%d",&n);
        if(n<=2) puts("+");
        else if(!prime[n]){
            if(n%4==1) puts("-");
            else puts("+");
        }
        else{
            bool f=0;
            for(int i=1;num[i]*num[i]<=n && i<=cnt;i++){//遍历质因数 
                while(n%num[i]==0){
                    if(num[i]%4==1) f=!f;//如果当前质因数项是负的，计数加一 
                    n/=num[i];
                }
            }
            if(n!=1 && n%4==1) f=!f;//可能除不完，检查一下 
            if(f) puts("-");
            else puts("+");
        }
    }
    return 0;
}