当且仅当n的质因数只有2和5
注意到,n的范围比较小,因此不用分解质因数
直接用一个较大的10的方幂去除n
看能否整除
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { const ll m=1e18; int t; cin>>t; while(t--) { int n; cin>>n; if(m%n) cout<<"NO"<<endl; else cout<<"YES"<<endl; } }
代码中m开1e9是不够的(亲测会挖)
简单证明一下。
考虑n以内的最大的2的方幂能含有多少个2
(最大的5的方幂能含有的5的个数一定比他小)
设
因此
m=1e16
是够用的
因为1e16的因数中有16个2