Submission #394584

#	Time	Username	Problem	Language	Result	Execution time	Memory
394584		NekoRolly	Strongbox (POI11_sej)	C++17	100 / 100	254 ms	5956 KiB

sej

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define fp(i,a,b) for(ll i=a ; i<b ; i++)
#define fn(i,a,b) for(int i=a ; i>=b ; i--)
#define ones(x) __builtin_popcount(x)
#define pb push_back
#define mk make_pair
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define dbg(x) cout << (#x) << " = " << x << " "
#define fini cout << "\n";
#define line cout << "-----------------------------------\n";
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef tree<
ll,
null_type,
less_equal<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
int read (){
    int x = 0, f = 1; char s = getchar();while (s < '0' || s > '9') {if (s == '-') f = -1; s = getchar();}
    while (s >= '0' && s <= '9') x = x * 10 + s - '0', s = getchar();
    return x * f; 
}

const ll M=25e4+7;
const ll N=1e9+7;
const ll inf=1e9;
const ll mod=1e9+7;
const ll mod2=998244353;

ll n,k;
ll a[M];
set<ll> ans;
vll dv;

void dfs(ll u,vpll pr){
	ans.erase(u);

	fp(i,0,pr.size())
		if (pr[i].ss && ans.count(u/pr[i].ff)){
			pr[i].ss--;
			dfs(u/pr[i].ff, pr);
			pr[i].ss++;
		}
}

void go(int ide){
	cin >> n >> k;

	fp(i,1,k+1) cin >> a[i];

	ll m = __gcd(n, a[k]);


	ll j = m;
	for (ll i=2; i*i<=j; i++)
		if (j%i == 0){
			dv.pb(i);
			while (j%i == 0) j /= i;
		}
	if (j>1) dv.pb(j);
	
	for (ll i=1; i*i<=m; i++)
		if (m%i == 0){
			ans.insert(i);
			ans.insert(m/i);
		}

	fp(i,1,k){
		vpll aux;
		ll x = __gcd(a[i], m);
		j = x;
		
		for (ll p : dv){
			ll e = 0;
			while (j%p == 0) j /= p, e++;
			aux.pb({p, e});
		}

		dfs(x, aux);
	}

	cout << (n/(*ans.begin())) << "\n";
}

int main(){
    fastio;
    int tst=1;
    // cin >> tst;
    // cout << fixed << setprecision(12);

    fp(i,0,tst) go(i+1);
  
    return 0;
}

Compilation message (stderr)

sej.cpp: In function 'void dfs(ll, vpll)':
sej.cpp:9:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 | #define fp(i,a,b) for(ll i=a ; i<b ; i++)
......
   56 |  fp(i,0,pr.size())
      |     ~~~~~~~~~~~~~                
sej.cpp:56:2: note: in expansion of macro 'fp'
   56 |  fp(i,0,pr.size())
      |  ^~

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 7 / 7
• Subtask 5: 7 / 7
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 8 / 8
• Subtask 14: 8 / 8