b****u 发帖数: 37 | 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
请问各位有什么好的解法? |
b****p 发帖数: 216 | 2 先找所有<=N的prime number. 然后找左边的combination,在找右边的combination? |
f*****e 发帖数: 2992 | 3 map行不行?
C
【在 b****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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
|
s*********s 发帖数: 318 | 4 1 * 4 = 4 * 1
这个也算吧。
【在 b****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先找所有<=N的prime number. 然后找左边的combination,在找右边的combination?
|
c****9 发帖数: 164 | 5 Hash_Map> Amap;
For(int i=0;i
For(int j=0;j
A[i*j] = Pair(i,j);
然后对hashmap做print |
r*******e 发帖数: 7583 | 6 map value 应该是 list of pairs 吧
【在 c****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Hash_Map> Amap; : For(int i=0;i: For(int j=0;j: A[i*j] = Pair(i,j); : 然后对hashmap做print
|
e*******i 发帖数: 56 | 7 #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);
} |
z*******o 发帖数: 4773 | |
g*******s 发帖数: 2963 | 9 用一个map的试试
#include
#include
#include |
e***a 发帖数: 1661 | 10 did u work it out?
C
【在 b****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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****u 发帖数: 37 | 11 我用的方法几乎和版上的一样,用hashtable存。但是他说有更好的方法。
【在 e***a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : did u work it out? : : C
|
b****u 发帖数: 37 | 12 不知道版上哪位大神有更好的解法。很好奇。
【在 b****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我用的方法几乎和版上的一样,用hashtable存。但是他说有更好的方法。
|
S********e 发帖数: 28 | 13 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*****g 发帖数: 4 | 14 A/C = D/B
然后找所有小于n的互质的pair,每个pair对应一个base等式。对于每一个base等式,
通过上下左右同乘以整数来找所有的等式。 |
h****g 发帖数: 105 | 15 感觉和permutation题类似。如果 两因子一样,那么这一对就只会产生一组解(1,1,1,1
and 2,2,2,2) 如果两因子不一样 会产生四组解(abab,abba,baab,baba.)只计算这些
base可能会减少复杂度 |
S******6 发帖数: 55 | 16 觉得用map做已经算比较优的算法了
期待更好算法。。。 |
x******e 发帖数: 18 | 17 同意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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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*********m 发帖数: 4740 | 18 this seems the right direction
【在 b****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先找所有<=N的prime number. 然后找左边的combination,在找右边的combination?
|
j**h 发帖数: 1230 | 19 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;
}
} |
b****u 发帖数: 37 | 20 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****p 发帖数: 216 | 21 先找所有<=N的prime number. 然后找左边的combination,在找右边的combination? |
f*****e 发帖数: 2992 | 22 map行不行?
C
【在 b****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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
|
s*********s 发帖数: 318 | 23 1 * 4 = 4 * 1
这个也算吧。
【在 b****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先找所有<=N的prime number. 然后找左边的combination,在找右边的combination?
|
c****9 发帖数: 164 | 24 Hash_Map> Amap;
For(int i=0;i
For(int j=0;j
A[i*j] = Pair(i,j);
然后对hashmap做print |
r*******e 发帖数: 7583 | 25 map value 应该是 list of pairs 吧
【在 c****9 的大作中提到】![](/moin_static193/solenoid/img/up.png) : Hash_Map> Amap; : For(int i=0;i: For(int j=0;j: A[i*j] = Pair(i,j); : 然后对hashmap做print
|
e*******i 发帖数: 56 | 26 #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);
} |
z*******o 发帖数: 4773 | |
g*******s 发帖数: 2963 | 28 用一个map的试试
#include
#include
#include |
e***a 发帖数: 1661 | 29 did u work it out?
C
【在 b****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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****u 发帖数: 37 | 30 我用的方法几乎和版上的一样,用hashtable存。但是他说有更好的方法。
【在 e***a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : did u work it out? : : C
|
|
|
b****u 发帖数: 37 | 31 不知道版上哪位大神有更好的解法。很好奇。
【在 b****u 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我用的方法几乎和版上的一样,用hashtable存。但是他说有更好的方法。
|
S********e 发帖数: 28 | 32 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*****g 发帖数: 4 | 33 A/C = D/B
然后找所有小于n的互质的pair,每个pair对应一个base等式。对于每一个base等式,
通过上下左右同乘以整数来找所有的等式。 |
h****g 发帖数: 105 | 34 感觉和permutation题类似。如果 两因子一样,那么这一对就只会产生一组解(1,1,1,1
and 2,2,2,2) 如果两因子不一样 会产生四组解(abab,abba,baab,baba.)只计算这些
base可能会减少复杂度 |
S******6 发帖数: 55 | 35 觉得用map做已经算比较优的算法了
期待更好算法。。。 |
x******e 发帖数: 18 | 36 同意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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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*********m 发帖数: 4740 | 37 this seems the right direction
【在 b****p 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 先找所有<=N的prime number. 然后找左边的combination,在找右边的combination?
|
j**h 发帖数: 1230 | 38 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**o 发帖数: 548 | 39 为什么?
【在 w*********m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : this seems the right direction
|
A*****o 发帖数: 284 | 40 献丑发个代码, 遍历两数乘积的因子组合, 同时需要控制下打印范围:
#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**t 发帖数: 893 | 41
【在 A*****o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 献丑发个代码, 遍历两数乘积的因子组合, 同时需要控制下打印范围: : #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**t 发帖数: 893 | 42 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 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 献丑发个代码, 遍历两数乘积的因子组合, 同时需要控制下打印范围: : #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*****d 发帖数: 105 | 43 我也是这个思路。先把所有abab的情况收集起来,然后找所有ab=cd的情况,这里注意
一下去重,可以约定必须c<=d。
,1
【在 h****g 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 感觉和permutation题类似。如果 两因子一样,那么这一对就只会产生一组解(1,1,1,1 : and 2,2,2,2) 如果两因子不一样 会产生四组解(abab,abba,baab,baba.)只计算这些 : base可能会减少复杂度
|
e***n 发帖数: 42 | 44 来个java的:
public static void twoProduct(int n){
Map> m = new HashMap
String>>();
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; i
for (int j=0; j
System.out.println(tmp.getValue().get(i) + "=" + tmp.
getValue().get(j));
}
}
}
} |
A*****o 发帖数: 284 | 45 没有太明白... 请给个反例?
【在 w**t 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 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.
|