leetcode 313. Super Ugly Number
1893 ワード
Write a program to find the nth super ugly number.
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
Time Limit Exceeded
Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.
Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.
#include "stdafx.h"
#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
bool is_ugly(int num,vector<int> primes)
{
int k=0;
while(k!=primes.size())
{
while(num%primes[k]==0)
{
num/=primes[k];
}
k++;
if(num==1)
return true;
}
return false;
}
int findnext(int tt,vector<int> primes,bool f)
{
bool flag=false;
if(!f)
while(!flag)
{
++tt;
flag=is_ugly(++tt,primes);
}
else
while(!flag)
{
flag=is_ugly(++tt,primes);
}
return tt;
}
int nthSuperUglyNumber(int n, vector<int>& primes)
{
if(n==1)
return 1;
if(n==2)
return primes[0]==1?primes[1]:primes[0];
vector<int>nums;
nums.push_back(1);
int k=1;
bool f=false;
if(primes[0]==2)
f=true;
while(k!=n)
{
nums.push_back(findnext(nums.back(),primes,f));
k++;
}
return nums.back();
}
};
int _tmain(int argc, _TCHAR* argv[])
{
Solution sl;
int aa[30]={7,19,29,37,41,47,53,59,61,79,83,89,101,103,109,127,
131,137,139,157,167,179,181,199,211,229,233,239,241,251};
vector<int>primes(aa,aa+30);
cout<<sl.nthSuperUglyNumber(100000,primes);
system("pause");
return 0;
}
Time Limit Exceeded