URAL – 2102 Michael and Cryptography 分解质因数+优化

C - Michael and Cryptography 分解质因数+优化

 Source

URAL - 2102

MySolution

题意：每一个数都可以表示为 ai^bi + ai+1^bi+1 + ...... an^bn，判断 sigma bi 是否等于 20

分解质因数+优化

用O(sqrt(n))的分解质因数的方法，然后优化，sum记录次方的值，

1、当sum >= 20 时直接break，不用管后面的;

2、当if(sum == 19) 如果当前 i^2 > now 如果 i <= now 则接下来有且只有一个质因数，直接break;

                         如果 i > now 也直接f = false;break;  

3、当前i的20 - sum次，已经大于now了，即接下来now也不可能使sum达到20，故直接break

此外 n == 1时额外判断为 No

复杂度 远小于O(sqrt(n))

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const LL maxn = 1e6 + 8;

inline LL mod(const LL &a, const LL &b)
{
    return a - a / b * b;
}

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("c.out", "w", stdout);
    LL T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    LL n;
    cin >> n;
    if(n == 1) cout << "No" << endl;
    else{
        LL sum = 0;
        bool f = true;
        LL temp, now;
        temp = (LL)((double)sqrt(n) + 1);
        now = n;
        for(LL i = 2; i <= temp; i++){ if(sum >= 20) break;
            if(mod(now, i) == 0){
                while(mod(now, i) == 0){
                    sum++;
                    now /= i;
                }
            }
            if(sum >= 20) break;
            if(sum == 19){
                if(pow(i + 1, 2) > now){
                    if(i + 1 <= now) break; else { f = false; break;} } } if((LL)pow(i + 1, 20 - sum) > now) {f = false; break;}

        }
        if(f && now != 1){
            sum++;
        }


        if(!f) cout << "No" << endl;
        else if(sum == 20) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx