Submission #893569

#	Time	Username	Problem	Language	Result	Execution time	Memory
893569		vjudge1	Toys (CEOI18_toy)	C++17	79 / 100	5043 ms	2120 KiB

toy

#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 2 * 1e5 + 10;
const ll mod = 1e9 + 7;

ll um(ll a, ll b){
	return ((1LL * a * b) % mod + mod) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
ll binpow(ll x, ll step){
	ll res = 1LL;
	while(step){
		if(step & 1) res = um(res, x);
		x = um(x, x);
		step /= 2;
	}
	return res;
}
ll n;
vector <ll> nw;
map <ll, bool> mp;
void calc(ll index, ll cur, ll can){
	//cout << index << " "<< cur << " " << can << endl;
	if(index == -1){
		if(cur == n) mp[can] = true;
		return;
	}
	calc(index - 1, cur, can);
	while(true){
		if(nw[index] * cur > n) break;
		cur *= nw[index];
		can += (nw[index] - 1);
		calc(index - 1, cur, can);
	}
}
int main() {
	ios::sync_with_stdio(false);
  	cin.tie(NULL);
  	cin >> n;
  	if(n == 1){
  		cout << 1 << endl;
  		cout << 0;
  		return 0;
  	}
  	for(ll i = 2; i * i <= n; i++){
  		if(n % i == 0){
  			nw.pb(i);
  			if(n / i != i) nw.pb(n/i);
  		}
  	}
  	nw.pb(n);
  	sort(nw.begin(), nw.end());
  	calc((ll)nw.size() - 1, 1LL, 0LL);
  	cout << mp.size() << endl;
  	for(auto u : mp){
  		cout << u.F << " ";
  	}
  	//ll cnt = 0;
  	//vector <pll> vec;
  	// for(ll i = 2; i * i <= n; i++){
  		// while(n % i == 0){
  			// n /= i;
  			// cnt++;
  		// }
  		// if(cnt > 0) vec.pb({cnt, i});
  	// }
  	// if(n > 0) vec.pb({1, n});
  	// for(auto u : vec){
  		// cout << u.F << " "<< u.S << endl;
  	// }
  return 0;
}

• Subtask 1: 19 / 19
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 21