题解：AT_abc161_f [ABC161F] Division or Subtraction

建议降黄或橙。

题目分析

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

$k \mid n$ ，即 $k$ 为 $n$ 的因数，枚举 $n$ 的因数，将 $n$ 中所有的 $k$ 除掉，设 $a$ 为使 $\frac{n}{k^a}$ 为整数的最大值，计 $\frac{n}{k^a} = m$ ，此时 $k \nmid m$ ，即 $k \nmid m - k$ ，所以后续只能进行减法操作，即判断 $m \bmod k$ 此时是否为 $1$ 即可。
$k \nmid n$ ，同上， $k \nmid (n - k)$ ，所以只能进行减法操作，即 $n \bmod k = 1$ 时 $k$ 满足条件，即 $(n - 1) \bmod k = 0$ 。此时求出 $n - 1$ 的因数个数即可。

注意：当

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

CPP

#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;
}

题解：AT_abc161_f [ABC161F] Division or Subtraction

文章操作

题目分析

AC Code

相关推荐

评论

题解：AT_abc161_f [ABC161F] Division or Subtraction