F - Division or Substraction

题意

给你一个N，问你有多少个K可以进行以下操作之后使得N为1。

• 若N可以整除K则N=N/K
• 否则N=N-K

$2\le N\le 1e122\le K\le N$2≤N≤1e122≤K≤N

思路

首先要知道一个前置知识：x和x+1一定互质。
反证法：设 $gcd(x,x+1)=a$gcd(x,x+1)=a
$x=nkx+1=mkx+1-x=1=(m-n)k$x=nkx+1=mkx+1−x=1=(m−n)k
$\frac{1}{k}=m-n$k1​=m−n
$\because x+1>x$∵x+1>x
$\therefore m>n$∴m>n
又因为m，n一定为正整数，而k一定为大于1的正整数，显然不成立，故x和x+1互质。

1. N对N-1的因子操作结果一定为余数1，故N-1的因子(>1)一定满足。
2. N的因子中有可能满足题意的，可以 $O\left(\sqrt{N}logN\right)$O(N ​logN)去检查。

最近看到很多人用lambda表达式做题，有空还得学一下。
一开始我不知道那个前置知识，所以我的想法是用set放每一个元素，set里的元素唯一，所以最后只要输出set的大小即可，也贴出来吧。
lambda表达式

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

int main() {
	ll n;cin>>n;
	ll res=0;
	for(ll i=1;i*i<=n-1;i++){
		if((n-1)%i==0){
			if(i>1) res++;
			if((n-1)/i!=i) res++;
		}
	}
	auto check=[&](ll a){
		ll x=n;
		while(x%a==0) x/=a;
		if(x%a==1) res++;
	};
	for(ll i=1;i*i<=n;i++){
		if(n%i==0){
			if(i>1) check(i);
			if(i!=n/i) check(n/i);
		}
	}
	cout<<res<<'\n';
}

set

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

int main() {
	ll n;cin>>n;
	set<ll>s;
	for(ll i=1;i*i<=n-1;i++){
		if((n-1)%i==0){
			if(i>1) s.insert(i);
			if((n-1)/i!=i) s.insert((n-1)/i);
		}
	}
	auto check=[&](ll a){
		ll x=n;
		while(x%a==0) x/=a;
		if(x%a==1) s.insert(a);
	};
	for(ll i=1;i*i<=n;i++){
		if(n%i==0){
			if(i>1) check(i);
			if(i!=n/i) check(n/i);
		}
	}
	cout<<s.size()<<'\n';
}