当前位置：首页 → 问答吧 → 挑战!!!

挑战!!!

时间：2014-04-27

来源：互联网

input

复制内容到剪贴板代码:2 3 4 5 6 7 8 9 10 11 12 13 48 59 96

output

复制内容到剪贴板代码:1,2
1,3
1,2,4
1,5
1,2,3,6
1,7
1,2,4,8
1,3,9
1,2,5,10
1,11
1,2,3,4,6,12
1,13
1,2,3,4,6,8,12,16,24,48
1,59
1,2,3,4,6,8,12,16,24,32,48,96

code

复制内容到剪贴板代码:#include <iostream>
#include <map>
#include <set>
#include <iterator>
using namespace std;

uintmax_t GCD(uintmax_t a, uintmax_t b)
{
uintmax_t t;
while(b)
{
t = b;
b = a % t;
a = t;
}
return a;
}

const std::map<uintmax_t, uintmax_t> Decompose(uintmax_t n)
{
static std::map<uintmax_t, std::map<uintmax_t, uintmax_t>> _factors;

if(n == 0 || n == 1) throw;
std::map<uintmax_t, uintmax_t> &result = _factors[n];

//find the exists...
if(!result.empty())
return result;

if(n == 2)
{
result[2] = 1;
return result;
}

auto _decompose = [&](uintmax_t n, uintmax_t a, std::map<uintmax_t, uintmax_t> &result)
{
uintmax_t gcd = GCD(n, a);
if(gcd != 1)
{
for(auto q : Decompose(gcd))
{
if(result.find(q.first) == result.end())
result[q.first] = q.second;
else
result[q.first] += q.second;
}
for(auto q : Decompose(n / gcd))
{
if(result.find(q.first) == result.end())
result[q.first] = q.second;
else
result[q.first] += q.second;
}
return true;
}
return false;
};

for(auto i = _factors.begin(); i != _factors.end() && i->first != n; ++i)
{
if(_decompose(n, i->first, result)) return result;
}

if(_decompose(n, 2, result)) return result;
for(uintmax_t i = 3; i * i <= n; i += 2)
{
if(_decompose(n, i, result)) return result;
}

//write prime...
result[n] = 1;

return result;
}

const std::set<uintmax_t> Factor(uintmax_t n)
{
std::set<uintmax_t> result{ 1 };

if (n == 0) throw;
if (n == 1) return result;

auto _factor = *Decompose(n).begin();
for (uintmax_t i = 0, k = _factor.first; i < _factor.second; ++i, k *= _factor.first)
{
result.insert(k);

auto temp = Factor(n / k);
result.insert(temp.begin(), temp.end());

for (auto _p : temp) result.insert(_p * k);
}

return result;
}

int main()
{
// your code goes here

uintmax_t a;

while(std::cin >> a)
{
auto _f = Factor(a);

for(auto _p : _f)
{
std::cout << _p;
if(_p == a)
std::cout << endl;
else
std::cout << ",";
}

}

return 0;
}

[ 本帖最后由 Susan﹏汪汪於 2014-4-12 11:54 PM 编辑 ]

作者: Susan﹏汪汪发布时间: 2014-04-27

相信无咩几个系楼主嘅对手啦，C++ 本人唔识, 是否楼主在做紧特别既算法呢？其实可以好简单化架，以input和output既数字来睇，两个for loop加比较是否可整数除，再加个line feed即可唔系吗

作者: me888 发布时间: 2014-04-27

引用:原帖由 me888 於 2014-4-14 09:39 PM 发表
相信无咩几个系楼主嘅对手啦，C++ 本人唔识, 是否楼主在做紧特别既算法呢？其实可以好简单化架，以input和output既数字来睇，两个for loop加比较是否可整数除，再加个line feed即可唔系吗

h ...

唔一定要用C++的

作者: Susan﹏汪汪发布时间: 2014-04-27

用loop黎做的确会快D...

作者: Susan﹏汪汪发布时间: 2014-04-27

无所谓效率快慢啦，今时今日电脑既计算速度，根本系微不足道啦， bubble sort(新机) 可以快过quick sort (用旧机)

作者: me888 发布时间: 2014-04-27

引用:原帖由 me888 於 2014-4-14 10:04 PM 发表
无所谓效率快慢啦，今时今日电脑既计算速度，根本系微不足道啦， bubble sort(新机) 可以快过quick sort (用旧机)

不过研究快速算法都好好玩

作者: Susan﹏汪汪发布时间: 2014-04-27

Are you serious?

引用:原帖由 me888 於 2014-4-14 22:04 发表
无所谓效率快慢啦，今时今日电脑既计算速度，根本系微不足道啦， bubble sort(新机) 可以快过quick sort (用旧机)

作者: a8d7e8 发布时间: 2014-04-27

I think so

作者: me888 发布时间: 2014-04-27

复制内容到剪贴板代码:<html>
<head>
</head>
<body>

<script language="JavaScript">

var rt = new Array(2,3,4,5,6,7,8,9,10,11,12,13,48,59,96);

for (var i=0;i<15;i++)
{
for (var j=1;j<=rt[i];j++)
{
if ( rt[i] % j==0 )
{ document.write((j));
if (j<rt[i]) { document.write(",");}

}
}
document.write("<br />");

}

</script>

</body>
</html>

[ 本帖最后由 me888 於 2014-4-15 09:03 AM 编辑 ]

作者: me888 发布时间: 2014-04-27

I see.

c + cpu1 * O(n^2) < c2 + cpu2 * O(nlogn)

I thought that N was veeeeeeery BIG

引用:原帖由 me888 於 2014-4-15 08:59 发表

var rt = new Array(2,3,4,5,6,7,8,9,10,11,12,13,48,59,96);

for (var i=0;i

作者: a8d7e8 发布时间: 2014-04-27

复制内容到剪贴板代码:std::set<uintmax_t> Factor(uintmax_t n)
{
if (n == 0) throw;
std::set<uintmax_t> result{ 1, n };

for (uintmax_t i = 2; i * i < n; ++i)
{
if (n % i == 0)
{
result.insert(i);
result.insert(n / i);
}
}

return result;
}

作者: Susan﹏汪汪发布时间: 2014-04-27

Haskell:

复制内容到剪贴板代码:main = interact factorAll
factor s = let n = read s :: Int
in show $ filter (\x -> n `mod` x == 0) [1..n]
factorAll input = unlines $ map factor $ words input

作者: fitcat07 发布时间: 2014-04-27

试下 fn.py

复制内容到剪贴板代码:>>> from fn import _
>>> l = [2,3,4,5,6,7,8,9,10,11,12,13,48,59,96]
>>> for i in range(len(l)):
... fi = filter(l[i]%_==0, range(1, l[i]+1))
... print (','.join(map(str, list(fi))))
...
1,2
1,3
1,2,4
1,5
1,2,3,6
1,7
1,2,4,8
1,3,9
1,2,5,10
1,11
1,2,3,4,6,12
1,13
1,2,3,4,6,8,12,16,24,48
1,59
1,2,3,4,6,8,12,16,24,32,48,96
>>>

作者: form5 发布时间: 2014-04-27

引用:原帖由 form5 於 2014-4-16 01:23 AM 发表
试下 fn.py>>> from fn import _
>>> l = [2,3,4,5,6,7,8,9,10,11,12,13,48,59,96]
>>> for i in range(len(l)):
... fi = filter(l%_==0, range(1, l+1))
... print (','.join(map(str, list(fi))))
. ...

fn.py ...

作者: bluenemo 发布时间: 2014-04-27

挑战!!!

热门阅读

热门下载