E

原题

题目大意

对于给出的一个n，找到一个m，使得n%m == S(m)，其中m<=n，S表示各位数字之和

遍历1~n显然不现实，那么能不能找m呢？

通过变化等式我们可以发现，n-S(m)取余m为0，也就是m得倍数，也就是m是其因子

因为位数为12，所以S(m)的取值范围不超过120，通过遍历S(m)，判断n-S(m)是否有因子m满足题意，即n%m == S(m)即可

要求给出有多少个m，其中找因子可以通过Pollard_Rho的算法和Miller-Rabin算法找到质因数，然后通过深搜组合质因子，求得所有因子

代码如下

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define LL __int128
#include<unordered_set>
#include <random>
static mt19937 myrand(time(0));//随机数
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
const ll prime[] = { 2,3,5,7,11,13,17,19,23,29,31,37 };
ll mul(ll x, ll y, ll mod) //使用__int128(部分编译器无法使用，需尝试)，正常效率
{
	return (__int128)x * y % mod;//防止溢出
}
ll qpow(ll x, ll y, ll p)//快速位幂，处理大数，防止溢出
{
	ll res = 1;
	while (y)
	{
		if (y & 1)res = mul(res, x, p);
		x = mul(x, x, p);
		y >>= 1;
	}
	return res;
}
bool MillerRabin(ll n, ll a)//判断质数
{
	ll d = n - 1, r = 0;
	while (!(d & 1))
		d >>= 1, r++;
	ll z = qpow(a, d, n);
	if (z == 1)return true; // 情况 1
	// 情况 2
	for (int i = 0; i < r; i++)
	{
		if (z == n - 1)return true;
		z = mul(z, z, n);
	}
	return false;
}
bool isPrime(ll n)
{
	if (n <= 1)return false;
	for (int i = 0; i < 11; i++)
	{
		if (n == prime[i])return true; // 特判 1
		if (n % prime[i] == 0)return false; // 特判 2
		if (!MillerRabin(n, prime[i]))return false;
	}
	return true;
}
ll Pollard_Rho(ll n)//分解质因数，倍增优化
{
	ll c = myrand();
	auto f = [&](ll x) {return (((__int128)x * x + c) % n);  };//函数内定义函数，'&'表示全继承
	ll x = 0, y = 0, s = 1;
	for (int k = 1; k <<= 1; y = x, s = 1)
	{
		for (int i = 1; i <= k; i++)
		{
			x = f(x);
			s = (__int128)s * abs(x - y) % n;
			if (i % 127 == 0)
			{
				ll d = gcd(s, n);
				if (d > 1) return d;
			}
		}
		ll d = gcd(s, n);
		if (d > 1) return d;
	}
	return n;
}
vector<ll> factor;
void get_factor(ll n)
{

	if (n == 1)
	{
		return;
	}
	if (n == 4)//特判
	{
		factor.push_back(2);
		factor.push_back(2);
		return;
	}
	if (isPrime(n))
	{
		factor.push_back(n);
		return;
	}
	ll x = n;
	while (x == n) x = Pollard_Rho(n);//随机性很强
	get_factor(x), get_factor(n / x);
}
long long sum(long long m) {//求和
	long long sum = 0;
	while (m > 0) {
		sum += m % 10;
		m /= 10;
	}
	return sum;
}
ll n = 0;
ll ans = 0;
void dfs(ll s, ll i, ll m = 1) {//深搜
	if (i >= factor.size())
    {
        ans +=( n % m == s && sum(m) == s);
        return;
    }
	ll j = i;
	for (; j < factor.size() && factor[i] == factor[j]; j++);//跳过重复的质因子
	for (ll k = 0; k <= j - i; k++)//对于该质因子的k次方
    {
        dfs(s, j, m);
        m *= factor[i];
    }
}
void solve()
{
	cin >> n;
	ans = 0;
	for (ll i = 1; i < 110 && i<n; i++)
	{
		if (i >= n) break;
		factor.clear();
		get_factor(n - i);
		sort(factor.begin(), factor.end());
		dfs(i, 0);
	}
	cout << ans << endl;
}
int main() {
	int t;
	cin >> t;
	while (t--) 
	{

		solve();
	}
	return 0;
}