[Codeforces] 912E. Prime Gift

題目連結:http://codeforces.com/contest/912/problem/E
記錄一下覺得滿有趣的題目。 首先要知道$10^{18}$以內的只包含包個質因數的數，大約只有$10^6~10^7$種左右，所以我們可以把給定的$n$個質數採用砍半枚舉產生出所有$10^{18}$以內僅包含給定的質因數的數，但是因為如果真的把全部都長出來了會太大，所以我們還可以二分搜第k大會是誰，這樣就只要知道比某個數小的數字有幾個就好了，而計算這個的方法很簡單，就枚舉一邊，再二分搜另外一邊即可。 
#include <bits/stdc++.h>
using namespace std;
typedef uint64_t llu;
#define PB push_back
#define ALL(x) begin(x), end(x)
const llu C = 1000000000000000000LL;

llu primes[20], p1[10], p2[10];
vector<llu> num1, num2;

inline llu calc(llu);
void dfs(int,llu,llu[],int,vector<llu>&);

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n; cin>>n;
	for(int i=0;i<n;i++) cin>>primes[i];
	sort(primes, primes+n);
	int n1 = 0, n2 = 0;
	for(int i=0;i<n;i+=2) p1[n1++] = primes[i];
	for(int i=1;i<n;i+=2) p2[n2++] = primes[i];
	dfs(0, 1, p1, n1, num1);
	dfs(0, 1, p2, n2, num2);
	sort(ALL(num1)); num1.resize(distance(num1.begin(), unique(ALL(num1))));
	sort(ALL(num2)); num2.resize(distance(num2.begin(), unique(ALL(num2))));
	llu k; cin>>k;
	llu l = 0, r = C;
	while(r-l > 1){
		llu mid = (l+r)>>1;
		if(calc(mid) >= k) r = mid;
		else l = mid;
	}
	cout << r << '\n';
	return 0;
}

void dfs(int id, llu x, llu p[], int n, vector<llu>& ret){
	if(x > C) return;
	if(id==n){
		ret.PB(x);
		return;
	}
	dfs(id+1, x, p, n, ret);
	if(x <= C/p[id]) dfs(id, x*p[id], p, n, ret);
}

inline llu calc(llu x){
	llu ret = 0;
	for(auto i: num1){
		llu dis = distance(num2.begin(), upper_bound(ALL(num2), x/i));
		if(dis == 0) break;
		ret += dis;
	}
	return ret;
}

留言

張貼留言

這個網誌中的熱門文章

[TIOJ] 1094. C.幼稚國王的獎賞

題目連結: http://tioj.infor.org/problems/1094 這題有三種作法，一種是我看完馬上想到的砍半枚舉後套trie #include <bits/stdc++.h> using namespace std; const int LOG_C = 20; const int N = 30 + 5; inline int two(int x){return 1<<x;} class Trie{ private: static constexpr int MEM = 5000000; struct node{ int lc, rc; node(): lc(0), rc(0){} } nodes[MEM]; int mem_, root; inline int new_node(){ assert(mem_ < MEM); nodes[mem_] = node(); return mem_++; } void insert(int x, int& cur, int d){ if(!cur) cur = new_node(); if(d == -1) return; if(x & two(d)) insert(x, nodes[cur].rc, d-1); else insert(x, nodes[cur].lc, d-1); } int query(int x, int cur, int d){ if(d == -1) return 0; if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc); int ret = 0; if(nodes[cur].rc) ret = query(x, nodes[cur].rc, d-1) + two(d); else ret = query(x, nodes[cur].lc, d-1); if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc); return ret; } public: void init(){
閱讀完整內容

[IOJ] 19. 啦啦啦

題目連結: http://ioj.infor.org/problems/19 因為$xor$有神奇(?的性質$a \oplus b = c \Longrightarrow a \oplus c = b$，所以就$O(n)$掃過去建好表，再$O(n)$掃一遍加起來，值得注意的是因為$a \oplus 0 = a$，所以若$x=0$，那要再減掉所有數的個數(自己不能算) #include <stdio.h> void gn(int &_){ _=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')_=_*10+c-'0',c=getchar(); } int MiccWan[100000 + 10]; int wayneTu[1000000 + 10] = {0}; int main(){ int t,x; long long edisonhello=0; gn(t);gn(x); for(int i=0;i<t;i++){ gn(MiccWan[i]); wayneTu[MiccWan[i]^x]++; } for(int i=0;i<t;i++){ edisonhello+=wayneTu[MiccWan[i]]; } if(x==0) edisonhello-=t; printf("%lld",edisonhello>>1); return 0; }
閱讀完整內容

[IOJ] 14. 費氏數列問題

題目連結: https://ioj.infor.org/problems/14 由題目可看出這是一個標準的線性遞迴，而居然是線性遞迴的話，那都可以用矩陣乘法搭配快速冪來讓時間複雜度降到$O(m^3 \log_2{(n-m)})$，然後不難發現其要用的$1 \times m$橫矩陣是$\left( \begin{array}{clr} 1 & 1 & \cdots & 1 \end{array} \right)$，而$m \times m$正方形矩陣則是$\left( \begin{array}{clr} k_{1} & 1 & 0 & 0 & \cdots \\ k_{2} & 0 & 1 & 0 & \cdots \\ k_{3} & 0 & 0 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ k_{m} & 0 & 0 & 0 & \cdots \end{array} \right)$至於會溢位的部分則按照題敘，每次在做加法乘法之類的時候都模一次$10^9+7$，因為可以證明先算再模跟先模再算再模都會得到相同的結果的。 #include <stdio.h> #include <algorithm> typedef long long lld; const lld mmdd = 1000000007; lld m1[110][110]={0}; auto aas = new lld [110][110]; lld n,m; void qPow(lld); void matrixTimes(lld[][110],lld[][110],lld[][110]); int main(){ scanf("%lld %lld",&n,&m); for(lld i=0;i<m;i++){ scanf("%lld",&m1[i][0]); if(i+1<m) m1[i][i+1] = 1; }
閱讀完整內容