hiho一下第88周《Coordinates》题目分析

1
0

题目大意

给定数字P,Q，求出所有P和Q的约数p,q能够组成的不重复数字对(p,q)

解题思路

作为本场比赛的第一题，本题的难度在于考察选手是否有基本的编程能力。

本题中需要求出P,Q所有约数组成的数字对，因此我们需要先将P,Q两个数字所有的约数分别找出来，再依次组合后输出。

求解一个数字P的所有约数，可以依次枚举1..P分别进行检查是否能够被P整除，也可以降低复杂度只枚举1..sqrt(P)，具体实现可以参考如下伪代码：

// 枚举 1.. P
p_count = 0
For i = 1 .. P
    If (P mod i == 0) Then
        p_divisors[p_count] = i
        p_count = p_count + 1
    End If
End For

// 枚举 1 .. sqrt(P)
p_count = 0
For i = 1 .. sqrt(P)
    If (P mod i == 0) Then
        p_divisors[p_count] = i
        p_count = p_count + 1
        If (P div i > i) Then 
            // 这个判断语句的作用是为了防止当 P 为平方数时
            // 将 sqrt(P) 重复加入约数中
            p_divisors[p_count] = P div i
            p_count = p_count + 1
        End If
    End If
End For
// 用这种方法得到的约数序列需要进行排序
Sort(p_divisors)

在得到p_divisors和q_divisors之后，再通过双重循环，即可将所有的数字对打印出来：

For i = 0 .. p_count - 1
    For j = 0 .. q_count - 1
        Output(p_divisors[i] + ' ' + q_divisors[j])
    End For
End For

到此，本题也就顺理解决。

15 answer(s)

0

为什么有人做得那么快?

"0:16:04"这样的是怎么做到的有人知道吗？

0

include

include

using namespace std;

int main(){

int P, Q;
scanf("%d%d", &P, &Q);
int arrP[500], arrQ[500];
int indexP = 0, indexQ = 0;
for(int i = 1; i <= sqrt(P) + 1; ++i)
    if((P % i == 0) && (i != P))
        arrP[indexP++] = i;
arrP[indexP++] = P;
for(int i = 1; i <= sqrt(Q) + 1; ++i)
    if((Q % i == 0) && (i != Q))
        arrQ[indexQ++] = i;
arrQ[indexQ++] = Q;
for(int i = 0; i < indexP; ++i)
    for(int j = 0; j < indexQ; ++j)
        printf("%d %d\n", arrP[i], arrQ[j]);
return 0;

}

0

即使只枚举1~sqrt(n)也不需要sort啊，两个数组之后再连接不就好了

0

include

include

include

using namespace std;

void divisor(int num, int sq, int * div, int & ct) {

ct = 0;
for(int i = 1; i <= sq; i++) {
    if(num % i == 0) {
        div[ct++] = i;
        div[ct++] = num / i;
    }
}

if(num == (sq * sq))    ct--;

sort(div, div+ct);

//for(int i = 0; i < ct; i++)
//    cout << div[i] << " ";

return;

}

int main() {

int P, Q;
cin >> P >> Q;

int p_sqrt = sqrt(P), q_sqrt = sqrt(Q);
int pcount, qcount;

int * pd = new int[p_sqrt];
divisor(P, p_sqrt, pd, pcount);

int * qd = new int[q_sqrt];
divisor(Q, q_sqrt, qd, qcount);

for(int i = 0; i < pcount; i++) {
    for(int j = 0; j < qcount; j++) {
        cout << pd[i] << " " << qd[j] << endl;
    }
}

return 0;

}

0

请教下，为什么我自己的DEV-C++运行没有问题，同样的代码，提交上去给的结果就是RE啊？

1

include "iostream"

using namespace std;

define M 100

int main(){ int P,Q; int Poo[M],Qoo[M]; int P_count=0,Q_count=0;

cin>>P>>Q;

for(int i=1;i<=P;i++)
    if(P%i==0){
        Poo[P_count]=i;
        P_count++;
    }

for(int j=1;j<=Q;j++)
    if(Q%j==0){
        Qoo[Q_count]=j;
        Q_count++;
    }

for(int i=0;i<P_count;i++)
    for(int j=0;j<Q_count;j++)
        cout<<"("<<Poo[i]<<","<<Qoo[j]<<")"<<endl;

}

0

0.0

0

1

0

求教。。。。上周比赛第2题怎么做？说说思路就行。。。。谢了。。。

  • 二分+模拟

  • 能说得再详细些么？O(∩_∩)O谢谢！

  • 使用二分法枚举缓冲区大小，然后暴力解么？

  • 二分法枚举缓冲区大小，然后用堆模拟出数据包被处理的顺序。总复杂度是O(NlogNlogN)的。

  • 求问上周比赛第三题怎么个思路。。。？

  • @gtdzx，已过，多谢指点。。。

  • 同求第3题思路。。多谢。。

  • 添加评论
  • ✖reply
0

include

0

include using name space;

int main(){ int P=12; int Q=18; int p,q; for(int i=1;i<=P/2;i++){

}

}

0

int

0

P,Q = raw_input().split(' ') P, Q = int(P), int(Q) p = [P] q = [Q] for i in range(P/2): if P%(i+1) == 0: p.append(i+1) for i in range(Q/2): if Q%(i+1) == 0: q.append(i+1)
for i in range(len(p)): for j in range(len(q)): print p[i], q[j]

  • 怎么提交啊，我去！

  • 从顶级导航的"hiho一下"点进去提交： http://hihocoder.com/contest/hiho88

  • 添加评论
  • ✖reply
0

这真的是微软笔试题么？这么简单？

  • 毕竟有四道题，有时候前面题目简单是为了多留些时间给后面的题目。不过一般第一题都很简单。

  • 添加评论
  • ✖reply
0

题目状态不太对劲，十佳代码都出来了。

  • 是啊，而且今天10点才出来，往常都是8点就出来了

  • 谢谢反馈，改过来了。

  • 添加评论
  • ✖reply

write answer 切换为英文 切换为中文

转发分享

▲