4128: Tao God and Jiong King II
Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 303  Solved: 22

Description
Today Tao God invite Jiong King to join his party of heaven.It’s wellknown to us,Tao God is the leader of heaven and Jiong King is the leader of hell.To welcome for Jiong King’coming,Tao God come up with a game to play with Jiong King.Tao God select a number A and Jiong King select a number B.Their value of happiness is the sum of the common divisors of A and B.
If X can be divided by Y, we call Y is a divisor of X. For example, 3 is a divisor of 6.Now, give you Tao God’selection A and Jiong King’selection B,please help them calculate their value of happiness.



Input
The input file consists of multipe test cases.

Each tast case only contains two numbers A and B.

(1 <= A, B <= 100000000)

 


Output
Output their value of happiness.




Sample Input
5 10
6 8

Sample Output
6
3

HINT

我写的代码，交上去是超时的。。。这道题要用什么方法解？
#include<stdio.h>
#include<string.h>
int main()
{
    long int A,B,t,i;
    int s;
    while(scanf("%d%d",&A,&B)!=EOF)
    {
        if(A>B)
        {A=t;A=B;B=t;}
        s=0;
        for(i=1;i<=A;i++)
        {
            if(A%i==0&&B%i==0)
            {
                s+=i;
            }
        }
        printf("%d\n",s);
    }
    return 0;
}

。

我想到一个, 就是先求出最大公因数,
再把最大公因数分解因子,
然后求和,
如果最大公因数是1,结果就是1, 如果不是1, 结果就要加1.

你的算法超时是因为如果A是最大值1亿, for循环要循环1亿次,
我的思路是, 首先最大的是两个数的最大公约数, 第二, 最小的是1, 第三, 其它的公因数都是最大公因数的因子.
发个代码讨论一下:

#include <stdio.h>

int main()
{
    int a, b;      
    int n;      // 最大公约数
    int s;      // 因子之和
    int i;

    while (scanf("%d%d", &a, &b) == 2) {    // 多组数据输入
        s = 1;                              // 因为每个结果都有最小的1, 所以直接初始化为1.
        n = a%b;
        if (n != 1) {                        // n 大于1时, 求最大公约数
            while (n) {
                a = b;
                b = n;
                n = a%b;
            }
            s += b;                         // 加上最大公约数
            for (i = 2; i <= b/2 ; i++) 
                if (b%i == 0)
                    s += i;                   // 加上最大公约数的因子.
     }
        printf("%d\n", s);
    }
    return 0;
}

[ 本帖最后由 pangshch 于 2014-1-14 14:50 编辑 ]

之前求因子的算法错了, 已修改,


[ 本帖最后由 pangshch 于 2014-1-14 14:51 编辑 ]

好像for循环还可以优化一下:

#include <math.h>

for (i = 2; i <= sqrt(b); i++)
                if (b%i == 0) {
                    s += b/i;　　　// 当i*i=b时，　会多加一次i的值，　如b=16, i和b/i都等于4.结果多4
                    s += i;
                    if (i * i == b)   // 用if减去多加的i
                        s -= i;
                }

把b/2 改成sqrt(b), 加一个if()判断，这样多一个判断语句, 但是for()循环减少了很多次,
如,a = 1亿, b = 1百万, b/2要循环50万次, sqrt(b)只要循环1000次.

不行，还是TLE啊。。。。

灰常感谢，优化后的AC啦

之前的思路也是第二个sqrt(b), 只是后面发现不对(当时没有加s+=b/i), 就改成了b/2,
然后又发现效率只提高了一半, 所以又回到了sqrt(b), 修改后循环最坏的情况是a = b = 1亿, 最多循环1万次, 你的是1亿, 我的第一个是5000万,