夏日牛仔裙！ - 未名空间MITBBS历史存档

b*u2010-07-07 07:07

1 楼

Question: For some N, print all the solutions of A * B = C * D where A, B, C
, D are all 1-N.
eg. n=2
print:
1 * 1 = 1 * 1
1 * 2 = 1 * 2
1 * 2 = 2 * 1
2 * 1 = 1 * 2
2 * 1 = 2 * 1
2 * 2 = 2 * 2
请问各位有什么好的解法？

I*e2010-07-07 07:07

2 楼

大家讨论讨论？

b*p2010-07-07 07:07

3 楼

先找所有<=N的prime number. 然后找左边的combination，在找右边的combination?

f*s2010-07-07 07:07

4 楼

牛仔短裙？？

f*e2010-07-07 07:07

5 楼

map行不行？

C

【在 b****u 的大作中提到】

: Question: For some N, print all the solutions of A * B = C * D where A, B, C
: , D are all 1-N.
: eg. n=2
: print:
: 1 * 1 = 1 * 1
: 1 * 2 = 1 * 2
: 1 * 2 = 2 * 1
: 2 * 1 = 1 * 2
: 2 * 1 = 2 * 1
: 2 * 2 = 2 * 2

I*e2010-07-07 07:07

6 楼

连衣裙或者短裙。。但是我觉得牛仔裙都是看起来很美。穿上身整个色彩就很plain.

【在 f**********s 的大作中提到】

: 牛仔短裙？？

s*s2010-07-07 07:07

7 楼

1 * 4 = 4 * 1
这个也算吧。

【在 b****p 的大作中提到】

: 先找所有<=N的prime number. 然后找左边的combination，在找右边的combination?

n*y2010-07-07 07:07

8 楼

no need to discuss...
we need to see the truth....

c*92010-07-07 07:07

9 楼

Hash_Map> Amap;
For(int i=0;iFor(int j=0;jA[i*j] = Pair(i,j);
然后对hashmap做print

l*32010-07-07 07:07

10 楼

你的新鞋子到了吗？奔一个，，挺期待的

r*e2010-07-07 07:07

11 楼

map value 应该是 list of pairs 吧

【在 c****9 的大作中提到】

: Hash_Map> Amap;
: For(int i=0;i: For(int j=0;j: A[i*j] = Pair(i,j);
: 然后对hashmap做print

f*s2010-07-07 07:07

12 楼

软软的牛仔布还挺好看的，不太喜欢很硬的牛仔短裙。
看麻豆穿很好看，我穿不来。

plain.

【在 I*****e 的大作中提到】

: 连衣裙或者短裙。。但是我觉得牛仔裙都是看起来很美。穿上身整个色彩就很plain.

e*i2010-07-07 07:07

13 楼

#include
#include
#include
using namespace std;
void printEqProducts(int n)
{
typedef unordered_multimap > MyMap;
typedef unordered_map ProductMap;
MyMap resMap;
ProductMap proMap;
for(int i=1; i<=n;i++)
for(int j=1;j<=n;j++)
{
resMap.insert( MyMap::value_type(i*j, pair(i, j)) );
proMap.insert( pair(i*j,i*j) );
}
pair eqRange;
MyMap::const_iterator it1;
MyMap::const_iterator it2;
ProductMap::const_iterator it;
for(it=proMap.begin();it!=proMap.end(); ++it)
{
eqRange=resMap.equal_range(it->second);
for(it1=eqRange.first; it1!=eqRange.second; ++it1)
{
for(it2=eqRange.first; it2!=eqRange.second; ++it2)
{
cout<< it1->second.first <second.second<= "<< it2->second.first <second.second <}
}
}
}
int main()
{
printEqProducts(3);
}

I*e2010-07-07 07:07

14 楼

比如这件？大家觉得如何？

【在 n***y 的大作中提到】

: no need to discuss...
: we need to see the truth....

z*o2010-07-07 07:07

15 楼

N之间的任意i,j,
求i*j的所有因子.

f*s2010-07-07 07:07

16 楼

对了美女，你把家里的搭配包括鞋子，都奔上来给我们借鉴下。

【在 I*****e 的大作中提到】

: 比如这件？大家觉得如何？

g*s2010-07-07 07:07

17 楼

用一个map的试试
#include
#include
#include
using namespace std;
void factorMutiplication(int n)
{
// hash all combinations
map>> map;
for (int i=1;i<=n;++i)
for (int j=1; j<=n;++j)
map[i*j].push_back(make_pair(i,j));
// print all combinations
for (int i=1;i<=n;++i)
for (int j=1; j<=n;++j)
{
vector> match = map[i*j];
for(int k=0; kcout<<<<}
}
int main()
{
factorMutiplication(4);
cin.get();
return 0;
}

l*z2010-07-07 07:07

18 楼

好看。很青春，清爽。

e*a2010-07-07 07:07

19 楼

did u work it out?

C

【在 b****u 的大作中提到】

: Question: For some N, print all the solutions of A * B = C * D where A, B, C
: , D are all 1-N.
: eg. n=2
: print:
: 1 * 1 = 1 * 1
: 1 * 2 = 1 * 2
: 1 * 2 = 2 * 1
: 2 * 1 = 1 * 2
: 2 * 1 = 2 * 1
: 2 * 2 = 2 * 2

n*y2010-07-07 07:07

20 楼

that should look better
on a Chinese girl...

【在 I*****e 的大作中提到】

: 比如这件？大家觉得如何？

b*u2010-07-07 07:07

21 楼

我用的方法几乎和版上的一样，用hashtable存。但是他说有更好的方法。

【在 e***a 的大作中提到】

: did u work it out?
:
: C

f*s2010-07-07 07:07

22 楼

你穿这件一定好看。

【在 I*****e 的大作中提到】

: 比如这件？大家觉得如何？

b*u2010-07-07 07:07

23 楼

不知道版上哪位大神有更好的解法。很好奇。

【在 b****u 的大作中提到】

: 我用的方法几乎和版上的一样，用hashtable存。但是他说有更好的方法。

I*e2010-07-07 07:07

24 楼

不会自拍阿。我没有那种大镜子。只有半身的。鞋子到了。很PP.

【在 f**********s 的大作中提到】

: 对了美女，你把家里的搭配包括鞋子，都奔上来给我们借鉴下。

S*e2010-07-07 07:07

25 楼

Would it work if we change the equation to be 'A * B / C = D'?
That way, we would basically transform the original question to something
similar to '3Sum', with an extra condition that 'A * B % C == 0' must return
true.

z*62010-07-07 07:07

26 楼

我总脚着牛仔就要质地硬一点,有纹理感, 有水洗感的.
这种裙子感觉就是一般面料,染成蓝色而已. 我第一感觉不会认为他是牛仔裙.

【在 I*****e 的大作中提到】

: 不会自拍阿。我没有那种大镜子。只有半身的。鞋子到了。很PP.

E*g2010-07-07 07:07

27 楼

A/C = D/B
然后找所有小于n的互质的pair，每个pair对应一个base等式。对于每一个base等式，
通过上下左右同乘以整数来找所有的等式。

f*s2010-07-07 07:07

28 楼

哪天去ikea买一个全身镜回来。美女没有大镜子还得了。

【在 I*****e 的大作中提到】

: 不会自拍阿。我没有那种大镜子。只有半身的。鞋子到了。很PP.

h*g2010-07-07 07:07

29 楼

感觉和permutation题类似。如果两因子一样，那么这一对就只会产生一组解(1,1,1,1
and 2,2,2,2) 如果两因子不一样会产生四组解(abab,abba,baab,baba.)只计算这些
base可能会减少复杂度

I*e2010-07-07 07:07

30 楼

夏日倒是都流行这种软的牛仔面料的。否则会很热芭

【在 z*****6 的大作中提到】

: 我总脚着牛仔就要质地硬一点,有纹理感, 有水洗感的.
: 这种裙子感觉就是一般面料,染成蓝色而已. 我第一感觉不会认为他是牛仔裙.

S*62010-07-07 07:07

31 楼

觉得用map做已经算比较优的算法了
期待更好算法。。。

I*e2010-07-07 07:07

32 楼

出彩。但是只能在台上。走在街上岂不是太招摇了？

【在 f**********s 的大作中提到】

: 你穿这件一定好看。

x*e2010-07-07 07:07

33 楼

同意zhuangtuo的想法，伪代码如下：
for i=1:N
for j=1:N
for all common divisors k of i*j
if k<=N && (i*j)/k <= N
print (i,j,k, (i*j)/k)
时间复杂度：O(N^(5/2)), 还有没有更高效的方法？

C

【在 b****u 的大作中提到】

: Question: For some N, print all the solutions of A * B = C * D where A, B, C
: , D are all 1-N.
: eg. n=2
: print:
: 1 * 1 = 1 * 1
: 1 * 2 = 1 * 2
: 1 * 2 = 2 * 1
: 2 * 1 = 1 * 2
: 2 * 1 = 2 * 1
: 2 * 2 = 2 * 2

z*62010-07-07 07:07

34 楼

恩, 所以我印象中的牛仔裙就是细腿美女围在屁股上的一窄圈牛仔布而已..

【在 I*****e 的大作中提到】

: 出彩。但是只能在台上。走在街上岂不是太招摇了？

w*m2010-07-07 07:07

35 楼

this seems the right direction

【在 b****p 的大作中提到】

: 先找所有<=N的prime number. 然后找左边的combination，在找右边的combination?

I*e2010-07-07 07:07

36 楼

我随便闪一张。牛仔裙是去年的。说实话效果很plain。也不显身材。很短。坐着不方便

【在 z*****6 的大作中提到】

: 恩, 所以我印象中的牛仔裙就是细腿美女围在屁股上的一窄圈牛仔布而已..

j*h2010-07-07 07:07

37 楼

void printN(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
Set pairSet = getPairSet(i * j);
for (Pair pair : pairSet) {
System.out.println(i + "*" + j + "=" + pair.i + "*" +
pair.j);
}
}
}
}
Map> map = new HashMap>();
Set getPairSet(int product) {
if (map.containsKey(new Integer(product)))
return map.get(new Integer(product));
Set pairSet = new HashSet();
for (int i = 1; i < product; i++) {
if (product % i == 0)
pairSet.add(new Pair(i, product / i));
}
map.put(new Integer(product), pairSet);
return map.get(new Integer(product));
}
class Pair {
int i;
int j;
public Pair(int i, int j) {
this.i = i;
this.j = j;
}
}

I*e2010-07-07 07:07

38 楼

方便

【在 I*****e 的大作中提到】

: 我随便闪一张。牛仔裙是去年的。说实话效果很plain。也不显身材。很短。坐着不方便

b*u2010-07-07 07:07

39 楼

Question: For some N, print all the solutions of A * B = C * D where A, B, C
, D are all 1-N.
eg. n=2
print:
1 * 1 = 1 * 1
1 * 2 = 1 * 2
1 * 2 = 2 * 1
2 * 1 = 1 * 2
2 * 1 = 2 * 1
2 * 2 = 2 * 2
请问各位有什么好的解法？

f*s2010-07-07 07:07

40 楼

加条腰带更酷。

b*p2010-07-07 07:07

41 楼

先找所有<=N的prime number. 然后找左边的combination，在找右边的combination?

I*e2010-07-07 07:07

42 楼

是可以加。问题是下面太短。是那种有点像连衣短裤的设计。我加过。更显短了

【在 f**********s 的大作中提到】

: 加条腰带更酷。

f*e2010-07-07 07:07

43 楼

map行不行？

C

【在 b****u 的大作中提到】

: Question: For some N, print all the solutions of A * B = C * D where A, B, C
: , D are all 1-N.
: eg. n=2
: print:
: 1 * 1 = 1 * 1
: 1 * 2 = 1 * 2
: 1 * 2 = 2 * 1
: 2 * 1 = 1 * 2
: 2 * 1 = 2 * 1
: 2 * 2 = 2 * 2

z*62010-07-07 07:07

44 楼

竟然错过了..
要不再闪下. 这次我眼睛都不眨的等..

方便

【在 I*****e 的大作中提到】

: 是可以加。问题是下面太短。是那种有点像连衣短裤的设计。我加过。更显短了

s*s2010-07-07 07:07

45 楼

1 * 4 = 4 * 1
这个也算吧。

【在 b****p 的大作中提到】

: 先找所有<=N的prime number. 然后找左边的combination，在找右边的combination?

I*e2010-07-07 07:07

46 楼

嘿嘿

【在 z*****6 的大作中提到】

: 竟然错过了..
: 要不再闪下. 这次我眼睛都不眨的等..
:
: 方便

c*92010-07-07 07:07

47 楼

Hash_Map> Amap;
For(int i=0;iFor(int j=0;jA[i*j] = Pair(i,j);
然后对hashmap做print

y*l2010-07-07 07:07

48 楼

今年小牛仔上衣好像挺流行，里面配个柔软的连衣裙。
牛仔短裙似乎属于高中大学时代的故事，偶现在没办法欣赏了。个人认为裙子要不就要
软飘要不就要正式（pencil skirt)才好看。牛仔裙似乎不属于这两个categories.

【在 I*****e 的大作中提到】

: 嘿嘿

r*e2010-07-07 07:07

49 楼

map value 应该是 list of pairs 吧

【在 c****9 的大作中提到】

: Hash_Map> Amap;
: For(int i=0;i: For(int j=0;j: A[i*j] = Pair(i,j);
: 然后对hashmap做print

w*x2010-07-07 07:07

50 楼

在店里脑子一热买过超短的牛仔裙
但是觉得很不方便，坐下来弯腰什么的都容易走光
喜欢那种柔软的牛仔面料，带点飘逸感的，配个大草帽，很有夏天的感觉

e*i2010-07-07 07:07

51 楼

#include
#include
#include
using namespace std;
void printEqProducts(int n)
{
typedef unordered_multimap > MyMap;
typedef unordered_map ProductMap;
MyMap resMap;
ProductMap proMap;
for(int i=1; i<=n;i++)
for(int j=1;j<=n;j++)
{
resMap.insert( MyMap::value_type(i*j, pair(i, j)) );
proMap.insert( pair(i*j,i*j) );
}
pair eqRange;
MyMap::const_iterator it1;
MyMap::const_iterator it2;
ProductMap::const_iterator it;
for(it=proMap.begin();it!=proMap.end(); ++it)
{
eqRange=resMap.equal_range(it->second);
for(it1=eqRange.first; it1!=eqRange.second; ++it1)
{
for(it2=eqRange.first; it2!=eqRange.second; ++it2)
{
cout<< it1->second.first <second.second<= "<< it2->second.first <second.second <}
}
}
}
int main()
{
printEqProducts(3);
}

I*e2010-07-07 07:07

52 楼

是滴

【在 w*****x 的大作中提到】

: 在店里脑子一热买过超短的牛仔裙
: 但是觉得很不方便，坐下来弯腰什么的都容易走光
: 喜欢那种柔软的牛仔面料，带点飘逸感的，配个大草帽，很有夏天的感觉

z*o2010-07-07 07:07

53 楼

N之间的任意i,j,
求i*j的所有因子.

g*s2010-07-07 07:07

54 楼

用一个map的试试
#include
#include
#include
using namespace std;
void factorMutiplication(int n)
{
// hash all combinations
map>> map;
for (int i=1;i<=n;++i)
for (int j=1; j<=n;++j)
map[i*j].push_back(make_pair(i,j));
// print all combinations
for (int i=1;i<=n;++i)
for (int j=1; j<=n;++j)
{
vector> match = map[i*j];
for(int k=0; kcout<<<<}
}
int main()
{
factorMutiplication(4);
cin.get();
return 0;
}

e*a2010-07-07 07:07

55 楼

did u work it out?

C

【在 b****u 的大作中提到】

: Question: For some N, print all the solutions of A * B = C * D where A, B, C
: , D are all 1-N.
: eg. n=2
: print:
: 1 * 1 = 1 * 1
: 1 * 2 = 1 * 2
: 1 * 2 = 2 * 1
: 2 * 1 = 1 * 2
: 2 * 1 = 2 * 1
: 2 * 2 = 2 * 2

b*u2010-07-07 07:07

56 楼

我用的方法几乎和版上的一样，用hashtable存。但是他说有更好的方法。

【在 e***a 的大作中提到】

: did u work it out?
:
: C

b*u2010-07-07 07:07

57 楼

不知道版上哪位大神有更好的解法。很好奇。

【在 b****u 的大作中提到】

: 我用的方法几乎和版上的一样，用hashtable存。但是他说有更好的方法。

S*e2010-07-07 07:07

58 楼

Would it work if we change the equation to be 'A * B / C = D'?
That way, we would basically transform the original question to something
similar to '3Sum', with an extra condition that 'A * B % C == 0' must return
true.

E*g2010-07-07 07:07

59 楼

A/C = D/B
然后找所有小于n的互质的pair，每个pair对应一个base等式。对于每一个base等式，
通过上下左右同乘以整数来找所有的等式。

h*g2010-07-07 07:07

60 楼

感觉和permutation题类似。如果两因子一样，那么这一对就只会产生一组解(1,1,1,1
and 2,2,2,2) 如果两因子不一样会产生四组解(abab,abba,baab,baba.)只计算这些
base可能会减少复杂度

S*62010-07-07 07:07

61 楼

觉得用map做已经算比较优的算法了
期待更好算法。。。

x*e2010-07-07 07:07

62 楼

同意zhuangtuo的想法，伪代码如下：
for i=1:N
for j=1:N
for all common divisors k of i*j
if k<=N && (i*j)/k <= N
print (i,j,k, (i*j)/k)
时间复杂度：O(N^(5/2)), 还有没有更高效的方法？

C

【在 b****u 的大作中提到】

: Question: For some N, print all the solutions of A * B = C * D where A, B, C
: , D are all 1-N.
: eg. n=2
: print:
: 1 * 1 = 1 * 1
: 1 * 2 = 1 * 2
: 1 * 2 = 2 * 1
: 2 * 1 = 1 * 2
: 2 * 1 = 2 * 1
: 2 * 2 = 2 * 2

w*m2010-07-07 07:07

63 楼

this seems the right direction

【在 b****p 的大作中提到】

: 先找所有<=N的prime number. 然后找左边的combination，在找右边的combination?

j*h2010-07-07 07:07

64 楼

void printN(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
Set pairSet = getPairSet(i * j);
for (Pair pair : pairSet) {
System.out.println(i + "*" + j + "=" + pair.i + "*" +
pair.j);
}
}
}
}
Map> map = new HashMap>();
Set getPairSet(int product) {
if (map.containsKey(new Integer(product)))
return map.get(new Integer(product));
Set pairSet = new HashSet();
for (int i = 1; i < product; i++) {
if (product % i == 0)
pairSet.add(new Pair(i, product / i));
}
map.put(new Integer(product), pairSet);
return map.get(new Integer(product));
}
class Pair {
int i;
int j;
public Pair(int i, int j) {
this.i = i;
this.j = j;
}
}

h*o2010-07-07 07:07

65 楼

为什么？

【在 w*********m 的大作中提到】

: this seems the right direction

A*o2010-07-07 07:07

66 楼

献丑发个代码, 遍历两数乘积的因子组合, 同时需要控制下打印范围:
#include
#include
#include
using namespace std;
int n;
void printPair(int a, int b) {
int m = a * b;
int x, y;
for (x = m/max(a,b); x <= (int)sqrt(double(m)); x++) {
if (m%x == 0) {
y = m / x;
printf("%d * %d = %d * %d\n", a, b, x, y);
printf("%d * %d = %d * %d\n", a, b, y, x);
printf("%d * %d = %d * %d\n", b, a, x, y);
printf("%d * %d = %d * %d\n", b, a, y, x);
}
}
}
void printEquation(int n) {
if (n <= 0) {
return;
}
int a, b;
for (a = 1; a <= n; a++) {
printf("%d * %d = %d * %d\n", a, a, a, a);
for (b = a+1; b <= n; b++) {
printPair(a, b);
}
}
}
int main() {
cin >> n;
printEquation(n);
return 0;
}

w*t2010-07-07 07:07

67 楼

【在 A*****o 的大作中提到】

: 献丑发个代码, 遍历两数乘积的因子组合, 同时需要控制下打印范围:
: #include
: #include
: #include
: using namespace std;
: int n;
: void printPair(int a, int b) {
: int m = a * b;
: int x, y;
: for (x = m/max(a,b); x <= (int)sqrt(double(m)); x++) {

w*t2010-07-07 07:07

68 楼

x = m/max(a,b); 好像不对呀。2*3=1*6. we cannot start from 2
But the overall this direction seems right. I cannot see the extra space
taken by map solution provide gain for time complexity as big O.

【在 A*****o 的大作中提到】

: 献丑发个代码, 遍历两数乘积的因子组合, 同时需要控制下打印范围:
: #include
: #include
: #include
: using namespace std;
: int n;
: void printPair(int a, int b) {
: int m = a * b;
: int x, y;
: for (x = m/max(a,b); x <= (int)sqrt(double(m)); x++) {

w*d2010-07-07 07:07

69 楼

我也是这个思路。先把所有abab的情况收集起来，然后找所有ab=cd的情况，这里注意
一下去重，可以约定必须c<=d。

,1

【在 h****g 的大作中提到】

: 感觉和permutation题类似。如果两因子一样，那么这一对就只会产生一组解(1,1,1,1
: and 2,2,2,2) 如果两因子不一样会产生四组解(abab,abba,baab,baba.)只计算这些
: base可能会减少复杂度

e*n2010-07-07 07:07

70 楼

来个java的：
public static void twoProduct(int n){

Map> m = new HashMapString>>();

for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if (m.containsKey(i*j)){
m.get(i*j).add(Integer.toString(i) + '*' + Integer.toString(
j));
}
else{
ArrayList tmp = new ArrayList();
tmp.add(Integer.toString(i) + '*' + Integer.toString(j));
m.put(i*j, tmp);
}
}
}

for (Entry> tmp : m.entrySet()){
for (int i=0; ifor (int j=0; jSystem.out.println(tmp.getValue().get(i) + "=" + tmp.
getValue().get(j));
}
}
}
}

A*o2010-07-07 07:07

71 楼

没有太明白... 请给个反例?

【在 w**t 的大作中提到】

: x = m/max(a,b); 好像不对呀。2*3=1*6. we cannot start from 2
: But the overall this direction seems right. I cannot see the extra space
: taken by map solution provide gain for time complexity as big O.