oj.uz

Submission #394584

# Submission time Handle Problem Language Result Execution time Memory
394584 2021-04-27T01:40:28 Z NekoRolly Strongbox (POI11_sej) C++17
100 / 100
 254 ms 5956 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 328 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 3 ms 332 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 19 ms 204 KB Output is correct
4 Correct 14 ms 588 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 86 ms 1036 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 197 ms 332 KB Output is correct
4 Correct 70 ms 944 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 86 ms 960 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 109 ms 1080 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 137 ms 332 KB Output is correct
4 Correct 108 ms 1080 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 2000 KB Output is correct
2 Correct 47 ms 2120 KB Output is correct
3 Correct 109 ms 2724 KB Output is correct
4 Correct 197 ms 3884 KB Output is correct
5 Correct 165 ms 3020 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 4576 KB Output is correct
2 Correct 121 ms 4804 KB Output is correct
3 Correct 159 ms 4420 KB Output is correct
4 Correct 179 ms 3964 KB Output is correct
5 Correct 212 ms 4600 KB Output is correct

Subtask #13
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 5156 KB Output is correct
2 Correct 157 ms 5956 KB Output is correct
3 Correct 209 ms 5320 KB Output is correct
4 Correct 245 ms 5700 KB Output is correct
5 Correct 244 ms 5680 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 4892 KB Output is correct
2 Correct 158 ms 5912 KB Output is correct
3 Correct 200 ms 5444 KB Output is correct
4 Correct 254 ms 5828 KB Output is correct
5 Correct 254 ms 5700 KB Output is correct