8月15日小练

A N! HDU 1042 　　N的阶乘，大数相乘，这里的N<=10000，故可以用数组不用字符串。

代码： 1546ms

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 int a[40000];
 5 int main()
 6 {
 7     int n,i,j;
 8     while(~scanf("%d",&n))
 9     {
10         if(n==1 || n==0)    //n=1,n=0时另外讨论
11             {
12                 printf("1
"); 
13                 continue;
14             }
15         a[0]=1;    //[0]记录数组的长度
16         a[1]=1;
17         for(i=2;i<=n;i++)
18         {
19             int sum=0;   //清零
20             for(j=1;j<=a[0];j++)
21             {
22                 int temp=a[j]*i+sum;
23                 sum=temp/10;
24                 a[j]=temp%10;
25             }
26             while(sum)     //sum>10
27             {
28                 a[j]=sum%10;
29                 a[0]=j;
30                 sum/=10;
31                 j++;
32             }
33         }
34         for(i=a[0];i>=1;i--)      //反序输出
35             printf("%d",a[i]);
36         printf("
");
37     }
38     return 0;
39 }

B Moving Tables HDU 1050

左右各有200间房间，编号一边为奇数，一边为偶数，中间有一条走廊，走廊最多只能让一张桌子通过，问n组，分别从a搬到b，最少要花多少时间？

代码：贪心 0MS

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string.h>
 4 #include <algorithm>
 5 using namespace std;
 6 int main()
 7 {
 8     int T,a[205],x,y,n,i,j,sum;
 9     scanf("%d",&T);
10     while(T--)
11     {
12         sum=0;
13         memset(a,0,sizeof(a));   //清零
14         scanf("%d",&n);
15         for(i=1;i<=n;i++)
16         {
17             scanf("%d%d",&x,&y);
18             x=(x+1)/2;           //处理奇数偶数
19             y=(y+1)/2;
20             if(x>y)
21                 swap(x,y);     //交换x,y的值，有头文件algorithm
22             for(j=x;j<=y;j++)
23                 a[j]++;     //表示占用
24         }
25         for(i=1;i<=200;i++)
26             if(a[i]>sum)
27                 sum=a[i];     //同时最多要用到的
28         printf("%d
",sum*10);       //*10，每次10min
29     }
30     return 0;
31 }

C 变形课 HDU 1181 给出若干个字符串，0结束输入。若一个字符串的最后一个字符和另一个字符串的首字符相同，这两个字符串就变成一个，若能找到一个字符串一b开始，以m结束，则输出"Yes.",否则输"No.”

方法 DFS 本来我也是用DFS，但是后来写着写着，感觉不对.....因为每找一个字符串都要从第一个开始......╭(╯^╰)╮......然后我就放弃了.......　QAQ

代码： 15ms

 1 #include <stdio.h>
 2 #include <iostream>
 3 #include <string.h>
 4 using namespace std;
 5 int map[100005];
 6 int k,len;
 7 class A
 8 {
 9 public:
10     char x,y;
11     int l;
12 }a[100005];
13 void dfs(int i)
14 {
15     if(a[i].y=='m')    //尾字母为m，结束，k=1
16     {
17         k=1;
18         return ;
19     }
20     else
21         for(int j=1;j<len;j++)
22         {
23             if(map[j]!=0 || a[j].x!=a[i].y)     //不等于或者被标记，跳过
24                 continue;
25             map[j]=1;
26             dfs(j);  
27             map[j]=0;    //记得清零
28         }
29 }
30 int main()
31 {
32     char s[1000];
33     int j;
34     while(~scanf("%s",s))
35     {
36         memset(map,0,sizeof(map));
37         len=1;
38         k=0;
39         while(s[0]!='0')
40         {
41             a[len].l=strlen(s);    //长度
42             a[len].x=s[0];    //首字母
43             a[len].y=s[a[len].l-1];   //尾字母
44             len++;                                    //字符串的个数
45             scanf("%s",s);
46         }
47         for(j=1;j<len;j++)
48             if(a[j].x=='b')    //找到b开始的字符串
49             {   
50                 map[j]=1;    //标记
51                 dfs(j);
52             }
53         if(k)
54             printf("Yes.
");
55         else
56             printf("No.
");
57     }
58     return 0;
59 }

D Calculation 2 HDU 3501 给出一个数n，求比n小且不与n互质的数的和。

利用欧拉公式：初等数论与欧拉公式：

f(n)表示所有小于n，且与n互质的数的个数,n=p1^a1*p2^a2*p3^a3.......

f(n)=n(1-1/p1)(1-1/p2)(1-1/p3)........

所以可以求出num=n-1-f(n)，即与n不互质的数的个数，又由：对于整数n，如果x(x<n)与n互质，那么(n-x)也与n是互质的；同理如果x(x<n)与n不互质，那么(n-x)也与n是不互质的。所以两个不互质的数是关于中间数a，a-x和a+x的和就是n，所以sum=num*n/2;

代码： 15ms 本来还写了个0ms的，但是一样的代码再交一次却变成了15ms

#include <stdio.h>
#include <iostream>
using namespace std;
int oula(int n)
{
    int ans=n,i;
    for(i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            n=n/i;
            while(n%i==0)
                n=n/i;
            ans=ans/i*(i-1);      //欧拉公式
        }
        if(n==1)     //没有因子了
            break;
    }
    if(n!=1)
            ans=ans/n*(n-1);
    return ans;
}
int main()
{
    int n;
    __int64 sum,num;
    while(~scanf("%d",&n)&&n)
    {
        num=n-1-oula(n);
        sum=num*n/2;
        if(sum>=0)
            sum=sum%1000000007;    //取余
        else
            sum=sum+1000000007;       //防止溢出，否则会运行错误
        printf("%I64d
",sum);
    }
    return 0;
}

E An easy problem HDU 2601 给出一个数n<10^10,有i*j+i+j=n,满足0<i<=j，问有多少组这样的i,j。暴力肯定超时╮(╯▽╰)╭

i*j+i+j=(i+1)*(j+1)-1 所以：(i+1)*(j+1)=n+1；有：

代码： 2125ms

 1 #include <stdio.h>
 2 #include <iostream>
 3 using namespace std;
 4 int main()
 5 {
 6     int sum,T;
 7     __int64 n,i;
 8     scanf("%d",&T);
 9     while(T--)
10     {
11         scanf("%I64d",&n);
12         sum=0;
13         for(i=1;(i+1)*(i+1)-1<=n;i++)    //这样基本上就是从1~n^1/2了，而且是一重循环
14         {
15             if((n+1)%(i+1)==0)      //（n+1）/（i+1)=(j+1),如果(n+1)%(i+1)==0，则这样的j存在
16                 sum++;      
17         } 
18         printf("%d
",sum);
19     }
20     return 0;
21 }