QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#692084 | #9248. An Easy Math Problem | WaO_o# | TL | 1ms | 5608kb | C++20 | 1.7kb | 2024-10-31 13:47:03 | 2024-10-31 13:47:03 |
Judging History
This is the latest submission verdict.
- [2024-10-31 22:36:43]
- hack成功,自动添加数据
- (/hack/1098)
- [2024-10-31 22:13:58]
- hack成功,自动添加数据
- (/hack/1096)
- [2024-10-31 22:00:43]
- hack成功,自动添加数据
- (/hack/1095)
- [2024-10-31 13:47:03]
- Submitted
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define deg( x ) cout<<""#x"="<<x<<endl
#define endl '\n'
#define pll pair<int,int>
#define se second
#define fr first
const int N=1e5+10;
int gcd( int a , int b ){
if( b==0 ) return a;
return gcd( b , a%b );
}
int idx=0 , idn=0;
int fac[ N ] , num[ N ] , fan[ N ];
void dec( int x ){
idx=0;
//fac[ ++idx ]=1 , num[ idx ]=1;
for( int i=2; i*i<=x; i++ ){
if( x%i==0 ) fac[ ++idx ]=i , num[ idx ]=0;
while( x%i==0 ){
num[ idx ]+=1;
x/=i;
}
}
if( x!=1 ) fac[ ++idx ]=x , num[ idx ]=1;
idn=1; fan[ 1 ]=1;
for( int i=1; i<=idx; i++ ){
int en=idn , te=1;
int now=fac[ i ];
for( int k=1; k<=num[ i ]; k++ ){
te*=now;
for( int j=1; j<=en; j++ ) fan[ ++idn ]=fan[ j ]*te;
}
}
sort( fan+1 , fan+1+idn );
}
void solve(){
int n;
cin>>n;
//n=1e10;
dec( n );
int ans=0;
map< pair<int,int> , int > mp;
for( int i=1; i<=idn; i++ ){
int p=fan[ i ];
//cout<<p<<" ";
for( int j=i; j<=idn; j++ ){
int q=fan[ j ];
if( p*q > n ) break;
else if( n%( p*q )==0 ){
int g=gcd( p , q );
p/=g , q/=g;
if( mp[ { p ,q } ]==0 ){
mp[ { p , q } ]=1;
ans++;
}
}
}
}
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio( 0 );
cout.tie( 0 ); cin.tie( 0 );
int T=1;
cin>>T;
while( T-- ){
solve();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5608kb
input:
10 1 2 3 4 5 6 7 8 9 10
output:
1 2 2 3 2 5 2 4 3 5
result:
ok 10 lines
Test #2:
score: -100
Time Limit Exceeded
input:
2000 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 6469693230 646969323...