首页 > 代码库 > UVa 294 Divisors
UVa 294 Divisors
方法:数论 暴力
一个正整数n的因子个数d(n) 在number theory 是一个multiplicative function,有公式。利用素数筛选先求出 sqrt(1e9)内的素数,然后对范围内每一个数求解d(n), 去最大的即可。
code:
#include <cstdio> #include <cstring> #include <algorithm> #include <iostream> #include <string> #include <vector> #include <stack> #include <bitset> #include <cstdlib> #include <cmath> #include <set> #include <list> #include <deque> #include <map> #include <queue> #include <fstream> #include <cassert> #include <unordered_map> #include <cmath> #include <sstream> #include <time.h> #include <complex> #include <iomanip> #define Max(a,b) ((a)>(b)?(a):(b)) #define Min(a,b) ((a)<(b)?(a):(b)) #define FOR(a,b,c) for (ll (a)=(b);(a)<(c);++(a)) #define FORN(a,b,c) for (ll (a)=(b);(a)<=(c);++(a)) #define DFOR(a,b,c) for (ll (a)=(b);(a)>=(c);--(a)) #define FORSQ(a,b,c) for (ll (a)=(b);(a)*(a)<=(c);++(a)) #define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a)) #define FOREACH(a,b) for (auto &(a) : (b)) #define rep(i,n) FOR(i,0,n) #define repn(i,n) FORN(i,1,n) #define drep(i,n) DFOR(i,n-1,0) #define drepn(i,n) DFOR(i,n,1) #define MAX(a,b) a = Max(a,b) #define MIN(a,b) a = Min(a,b) #define SQR(x) ((LL)(x) * (x)) #define Reset(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define mp make_pair #define pb push_back #define all(v) v.begin(),v.end() #define ALLA(arr,sz) arr,arr+sz #define SIZE(v) (int)v.size() #define SORT(v) sort(all(v)) #define REVERSE(v) reverse(ALL(v)) #define SORTA(arr,sz) sort(ALLA(arr,sz)) #define REVERSEA(arr,sz) reverse(ALLA(arr,sz)) #define PERMUTE next_permutation #define TC(t) while(t--) #define forever for(;;) #define PINF 1000000000000 #define newline ‘\n‘ #define test if(1)if(0)cerr using namespace std; using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; typedef pair<int,int> ii; typedef pair<double,double> dd; typedef pair<char,char> cc; typedef vector<ii> vii; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll> l4; const double pi = acos(-1.0); vector<ll> primes; const int maxn = 31622; //sqrt(1e9) bitset<maxn+1> vis(0); void init() { for (ll i = 2; i <= maxn; ++i) { if (!vis[i]) primes.pb(i); for (auto p : primes) { if (p * i > maxn) break; vis[p*i] = true; if (i % p == 0) break; } } } int u, v; ll d(ll n) { ll ret = 1; for (auto p : primes) { if (p > n) break; if (n % p) continue; ll cnt = 1; while (n % p == 0) { n /= p; ++cnt; } ret *= cnt; } if (n != 1) ret *= 2; return ret; } void solve() { ll ans = -1, cnt = 0; for (ll i = u; i <= v; ++i) { ll ret = d(i); if (ret > cnt) { ans = i; cnt = ret; } } cout << "Between " << u << " and " << v << ", " << ans << " has a maximum of " << cnt << " divisors.\n"; } int main() { init(); int T; cin >> T; repn(kase, T) { cin >> u >> v; solve(); } }
由于范围比较小(1e4), 据说不预处理素数,对每个数直接暴力求因子也可以通过。
UVa 294 Divisors
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。