QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#168845#6566. Power of Divisorsucup-team134#AC ✓11ms7088kbC++144.1kb2023-09-08 23:38:482023-09-08 23:38:49

Judging History

你现在查看的是最新测评结果

  • [2023-09-08 23:38:49]
  • 评测
  • 测评结果:AC
  • 用时:11ms
  • 内存:7088kb
  • [2023-09-08 23:38:48]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>

#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<int D, typename T>struct vec : public vector<vec<D - 1, T>> {template<typename... Args>vec(int n = 0, Args... args) : vector<vec<D - 1, T>>(n, vec<D - 1, T>(args...)) {}};
template<typename T>struct vec<1, T> : public vector<T> {vec(int n = 0, T val = T()) : vector<T>(n, val) {}};
template<class T1,class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
int ri(){int x;scanf("%i",&x);return x;}
void rd(int&x){scanf("%i",&x);}
void rd(long long&x){scanf("%lld",&x);}
void rd(double&x){scanf("%lf",&x);}
void rd(long double&x){scanf("%Lf",&x);}
void rd(string&x){cin>>x;}
void rd(char*x){scanf("%s",x);}
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&p:x)rd(p);}
template<typename C,typename...T>void rd(C&a,T&...args){rd(a);rd(args...);}
//istream& operator>>(istream& is,__int128& a){string s;is>>s;a=0;int i=0;bool neg=false;if(s[0]=='-')neg=true,i++;for(;i<s.size();i++)a=a*10+s[i]-'0';if(neg)a*=-1;return is;}
//ostream& operator<<(ostream& os,__int128 a){bool neg=false;if(a<0)neg=true,a*=-1;ll high=(a/(__int128)1e18);ll low=(a-(__int128)1e18*high);string res;if(neg)res+='-';if(high>0){res+=to_string(high);string temp=to_string(low);res+=string(18-temp.size(),'0');res+=temp;}else res+=to_string(low);os<<res;return os;}

const int N=1e6+5;
vector<int> d(N);
bool prost(ll x){
	for(ll i=2;i*i<=x;i++){
		if(x%i==0){
			return 0;
		}
	}
	return 1;
}
int main()
{
	ll x;
	rd(x);
	if(x==1){
		printf("1\n");
		return 0;
	}
	for(int i=2;i<N;i++){
		if(d[i]==0){
			for(int j=i;j<N;j+=i){
				d[j]=i;
			}
		}
		bool ok=1;
		int cnt=0;
		ll tr=x;
		while(tr!=1){
			if(tr%i!=0){
				ok=0;
				break;
			}
			tr/=i;
			cnt++;
		}
		if(!ok){
			continue;
		}
		map<int,int> cn;
		int x=i;
		while(x!=1){
			cn[d[x]]++;
			x/=d[x];
		}
		int numDivs=1;
		for(auto p:cn){
			numDivs*=p.s+1;
		}
		if(numDivs==cnt){
			printf("%i\n",i);
			return 0;
		}
	}
	ll sq=sqrt(x);
	for(ll ans=sq-2;ans<=sq+2;ans++){
		if(ans*ans==x&&prost(ans)){
			printf("%lld\n",ans);
			return 0;
		}
	}
	printf("-1\n");
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 6828kb

input:

15625

output:

25

result:

ok single line: '25'

Test #2:

score: 0
Accepted
time: 0ms
memory: 6908kb

input:

64000000

output:

20

result:

ok single line: '20'

Test #3:

score: 0
Accepted
time: 11ms
memory: 6920kb

input:

65536

output:

-1

result:

ok single line: '-1'

Test #4:

score: 0
Accepted
time: 3ms
memory: 7072kb

input:

1

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 11ms
memory: 6832kb

input:

10

output:

-1

result:

ok single line: '-1'

Test #6:

score: 0
Accepted
time: 7ms
memory: 7016kb

input:

100

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0
Accepted
time: 1ms
memory: 6816kb

input:

10000

output:

10

result:

ok single line: '10'

Test #8:

score: 0
Accepted
time: 2ms
memory: 6776kb

input:

1000000000000000000

output:

100

result:

ok single line: '100'

Test #9:

score: 0
Accepted
time: 9ms
memory: 6900kb

input:

10372926089038969

output:

218089

result:

ok single line: '218089'

Test #10:

score: 0
Accepted
time: 5ms
memory: 6928kb

input:

10642944803293201

output:

10157

result:

ok single line: '10157'

Test #11:

score: 0
Accepted
time: 11ms
memory: 6896kb

input:

10646534823110209

output:

103182047

result:

ok single line: '103182047'

Test #12:

score: 0
Accepted
time: 1ms
memory: 7016kb

input:

1073741824

output:

32

result:

ok single line: '32'

Test #13:

score: 0
Accepted
time: 1ms
memory: 7088kb

input:

121

output:

11

result:

ok single line: '11'

Test #14:

score: 0
Accepted
time: 1ms
memory: 6960kb

input:

1296

output:

6

result:

ok single line: '6'

Test #15:

score: 0
Accepted
time: 11ms
memory: 6992kb

input:

16

output:

-1

result:

ok single line: '-1'

Test #16:

score: 0
Accepted
time: 8ms
memory: 6832kb

input:

16277421889

output:

127583

result:

ok single line: '127583'

Test #17:

score: 0
Accepted
time: 4ms
memory: 6948kb

input:

169

output:

13

result:

ok single line: '13'

Test #18:

score: 0
Accepted
time: 11ms
memory: 6776kb

input:

1985984

output:

-1

result:

ok single line: '-1'

Test #19:

score: 0
Accepted
time: 7ms
memory: 6804kb

input:

2

output:

-1

result:

ok single line: '-1'

Test #20:

score: 0
Accepted
time: 1ms
memory: 6804kb

input:

205891132094649

output:

243

result:

ok single line: '243'

Test #21:

score: 0
Accepted
time: 3ms
memory: 6808kb

input:

25

output:

5

result:

ok single line: '5'

Test #22:

score: 0
Accepted
time: 7ms
memory: 6976kb

input:

2626114239841

output:

1273

result:

ok single line: '1273'

Test #23:

score: 0
Accepted
time: 3ms
memory: 6976kb

input:

26269395104446321

output:

12731

result:

ok single line: '12731'

Test #24:

score: 0
Accepted
time: 7ms
memory: 7040kb

input:

3

output:

-1

result:

ok single line: '-1'

Test #25:

score: 0
Accepted
time: 2ms
memory: 6904kb

input:

3596345248055296

output:

88

result:

ok single line: '88'

Test #26:

score: 0
Accepted
time: 11ms
memory: 6940kb

input:

36

output:

-1

result:

ok single line: '-1'

Test #27:

score: 0
Accepted
time: 0ms
memory: 6916kb

input:

4

output:

2

result:

ok single line: '2'

Test #28:

score: 0
Accepted
time: 3ms
memory: 6900kb

input:

4096

output:

8

result:

ok single line: '8'

Test #29:

score: 0
Accepted
time: 3ms
memory: 6996kb

input:

49

output:

7

result:

ok single line: '7'

Test #30:

score: 0
Accepted
time: 7ms
memory: 6980kb

input:

5

output:

-1

result:

ok single line: '-1'

Test #31:

score: 0
Accepted
time: 11ms
memory: 6924kb

input:

576460752303423488

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0
Accepted
time: 7ms
memory: 6904kb

input:

581431415926321

output:

24112889

result:

ok single line: '24112889'

Test #33:

score: 0
Accepted
time: 8ms
memory: 7004kb

input:

6

output:

-1

result:

ok single line: '-1'

Test #34:

score: 0
Accepted
time: 0ms
memory: 6936kb

input:

64

output:

4

result:

ok single line: '4'

Test #35:

score: 0
Accepted
time: 4ms
memory: 6892kb

input:

656100000000

output:

30

result:

ok single line: '30'

Test #36:

score: 0
Accepted
time: 7ms
memory: 7088kb

input:

7

output:

-1

result:

ok single line: '-1'

Test #37:

score: 0
Accepted
time: 1ms
memory: 6948kb

input:

729

output:

9

result:

ok single line: '9'

Test #38:

score: 0
Accepted
time: 7ms
memory: 6996kb

input:

8

output:

-1

result:

ok single line: '-1'

Test #39:

score: 0
Accepted
time: 7ms
memory: 6808kb

input:

81

output:

-1

result:

ok single line: '-1'

Test #40:

score: 0
Accepted
time: 6ms
memory: 6904kb

input:

8527674378686464

output:

452

result:

ok single line: '452'

Test #41:

score: 0
Accepted
time: 1ms
memory: 6880kb

input:

9

output:

3

result:

ok single line: '3'

Test #42:

score: 0
Accepted
time: 7ms
memory: 7000kb

input:

982134461213542729

output:

994009

result:

ok single line: '994009'

Test #43:

score: 0
Accepted
time: 8ms
memory: 6812kb

input:

9992002399680016

output:

9998

result:

ok single line: '9998'

Test #44:

score: 0
Accepted
time: 11ms
memory: 6912kb

input:

999269311525198921

output:

-1

result:

ok single line: '-1'

Test #45:

score: 0
Accepted
time: 11ms
memory: 6772kb

input:

999949000866995087

output:

-1

result:

ok single line: '-1'

Test #46:

score: 0
Accepted
time: 7ms
memory: 7004kb

input:

999995482005103081

output:

-1

result:

ok single line: '-1'

Test #47:

score: 0
Accepted
time: 11ms
memory: 7000kb

input:

999999969999997921

output:

-1

result:

ok single line: '-1'

Test #48:

score: 0
Accepted
time: 7ms
memory: 6964kb

input:

999999999999999989

output:

-1

result:

ok single line: '-1'

Test #49:

score: 0
Accepted
time: 7ms
memory: 6820kb

input:

999999999999999999

output:

-1

result:

ok single line: '-1'