题解：AT_abc161_f [ABC161F] Division or Subtraction

JHR100330 · 2025-06-03 21:45:25 · 题解

建议降黄或橙。

题目分析

非常简单的分讨题，分两种情况。

注意：当 k = 1 时，1 \mid n，n 会一直除以 1，永远也不会变成 1，注意特判。

最后将两种情况的方案数加起来输出即可。

为何 k 不会重复呢？

我们会发现第一种情况 k \mid n，第二种情况 k \mid (n - 1)，由于 n 与 n - 1 互质，所以 n 与 n - 1 除 1 外没有公因数，而 1 我们已经排除掉了，所以两种情况的 k 不会重复。

时间复杂度约为 O(\sqrt{n})，计算 m 即 \frac{n}{k^a} 的复杂度可以忽略不计。

AC Code

#include<bits/stdc++.h>

using namespace std;

#define ll long long

ll n, ans = 0;

int main(){
    cin >> n;
    for(ll i = 1; i * i <= n; i ++){
        if(n % i == 0){
            ll x = n;
            if(i != 1){
                while(x % i == 0)
                    x /= i;
                if(x % i == 1) ans ++;
            }
            if(i * i == n) continue;
            x = n;
            if(n / i != 1){
                while(x % (n / i) == 0)
                    x /= (n / i);
                if(x % (n / i) == 1) ans ++;
            }
        }
    }
    n --;
    for(ll i = 1; i * i <= n; i ++){
        if(n % i == 0 ){
            if(i != 1) ans ++;
            if(i * i != n) ans ++;
        }
    }
    cout << ans;
    return 0;
}