CodeForces-1076B Divisor Subtraction 找规律

题目链接：https://vjudge.net/problem/CodeForces-1076B

题意：

题目要求给定一个数，要求每次减去其最小素因数（既是素数又是其因数），问直到n=0需要做几次运算。

分析：

首先如果n为素数，则其最小素因数就是它本身，故第一次运算n:=n-n即得0，只需要一次运算。当n为偶数时，素因子恒为2，故每次减2直到0，所以运算次数为n/2次，当n为奇数是，首先减一次最小素因子，因为最小素因子一定是奇数，故奇-奇=偶，变为偶数后就按上述做法求得运算次数即可。

总结如下：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <queue>

typedef long long ll;

using namespace std;

ll n;

bool prime(ll x) {

    for(ll i = ; i <= sqrt(x); i++) {

        if(x % i == )

            return false;

    }

    return true;

}

ll min_div(ll x) {

    for(ll i = ; i < n; i++) {

        if(x % i == )

            return i;

    }

}

int main(void) {

    while(scanf("%lld", &n) == ) {

        if(prime(n)) {

            printf("1\n");

            continue;

        }

        else if(n %  == ) {

            printf("%lld\n", n/);

            continue;

        }

        else {

            n -= min_div(n);

            printf("%lld\n", n/+);

        }

    }

}

巴特西

CodeForces-1076B Divisor Subtraction 找规律

最新文章

热门文章