丑数问题
leetcode 263
class Solution {vector<int>p={2,3,5};
public:bool isUgly(int n) {if(n==0)return 0;for(int x:p){while(n%x==0){n/=x;}}return n==1;}
};
leetcode 264
class Solution {
public:int nthUglyNumber(int n) {vector<int>ans(n+1);int p2=1,p3=1,p5=1;int v2=1,v3=1,v5=1;int p=1;while(p<=n){int m=min({v2,v3,v5});ans[p++]=m;if(m==v2){v2=ans[p2++]*2;}if(m==v3){v3=ans[p3++]*3;}if(m==v5){v5=ans[p5++]*5;}}return ans[n];}
};
leetcode 313
class Solution {struct st{long v;int i;int base;};
public:int nthSuperUglyNumber(int n, vector<int>& primes) {vector<long>ans(n+1);auto cmp=[](st a,st b){return a.v>b.v;};priority_queue<st,vector<st>,decltype(cmp)>pq(cmp);for(int x:primes){pq.push({1,1,x});}int p=1;while(p<=n){auto [v,i,b]=pq.top();pq.pop();if(v!=ans[p-1]){ans[p++]=v;}pq.push({ans[i]*b,i+1,b});}return (int)ans[n];}
};
leetcode 1201
