http://poj.org/problem?id=2407

Description

Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.
Input

就是求小于n且与n互质的数的个数

这题使用到欧拉函数：
对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。 例如φ(8)=4，因为1,3,5,7均和8互质。

φ函数的值
　　通式：φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1, p2……pn为x的所有质因数，x是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。
　　若n是质数p的k次幂，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因为除了p的倍数外，其他数都跟n互质。
　　欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)。
　　特殊性质：当n为奇数时，φ(2n)=φ(n), 证明于上述类似。

证明略

举例：
　　ψ（１０）＝１０×（１－１/２）×（１－１/５）＝４；
　　ψ（３０）＝３０×（１－１/２）×（１－１/３）×（１－１/５）＝８；
　　ψ（４９）＝４９×（１－１/７）＝４２。

我的代码：
#include<cstdio>
#include<iostream>
using namespace std;
#include<cmath>
int num[100000];
int f_Euler(int s,int a)//返回欧拉数的个数，s是数组num里数据的个数，a是原来输入数据，即n
{
double ans=a;
int i;
for(i=1;i<=s;i++)
{
   ans*=(1-1.0/num[i]);
}
return (int)(ans+0.1);
}
int main()
{
num[0]=1;//无用
int a,b,s,i,max,t;
while(scanf("%d",&a)&& a)
{
   t=a;
   s=0;
   //以下为分解质因数
   max=sqrt(double(a))+1;
   if(a%2==0){
    while(a%2==0){
     a=a/2;
    }
    num[++s]=2;
   }
   for(int i=3;i<=max;i+=2)
   {
    if(a%i==0){
     while(a%i==0){
      a=a/i;
     }
     num[++s]=i;
    }
   }
   if(a!=1)num[++s]=a;//分解最后剩下的数（可能大于sqrt(n)）
   printf("%d\n",f_Euler(s,t));
   memset(num,0,sizeof(int)*s);
}
return 0;
}

poj上一个优化的代码：
while(scanf("%d",&n),n != 0){
        if(n == 1){
            printf("0\n"); continue;
        }
        ans = n;
        for(int i = 2;i*i <= n;++i){
            if( n % i == 0 ){
                ans = ans - ans/i;//见注释
                while(n%i == 0){
                    n /= i;
                }
            }
        }
        // n is prime itself
        if(n != 1) ans = ans - ans / n;
        printf("%d\n",ans);
    }
注释：
ans = ans - ans/i其实就是
欧拉定理ans*=(1-1.0/num[i]);的简化版，深入理解欧拉函数后就知道是：ans/i是小于等于ans被i整除的数的个数..

附：
2-100欧拉函数表（供测试用）
　　n φ(n)
　　2 1
　　3 2
　　4 2
　　5 4
　　6 2
　　7 6
　　8 4
　　9 6
　　10 4
　　11 10
　　12 4
　　13 12
　　14 6
　　15 8
　　16 8
　　17 16
　　18 6
　　19 18
　　20 8
　　21 12
　　22 10
　　23 22
　　24 8
　　25 20
　　26 12
　　27 18
　　28 12
　　29 28
　　30 8
　　31 30
　　32 16
　　33 20
　　34 16
　　35 24
　　36 12
　　37 36
　　38 18
　　39 24
　　40 16
　　41 40
　　42 12
　　43 42
　　44 20
　　45 24
　　46 22
　　47 46
　　48 16
　　49 42
　　50 20
　　51 32
　　52 24
　　53 52
　　54 18
　　55 40
　　56 24
　　57 36
　　58 28
　　59 58
　　60 16
　　61 60
　　62 30
　　63 36
　　64 32
　　65 48
　　66 20
　　67 66
　　68 32
　　69 44
　　70 24
　　71 70
　　72 24
　　73 72
　　74 36
　　75 40
　　76 36
　　77 60
　　78 24
　　79 78
　　80 32
　　81 54
　　82 40
　　83 82
　　84 24
　　85 64
　　86 42
　　87 56
　　88 40
　　89 88
　　90 24
　　91 72
　　92 44
　　93 60
　　94 46
　　95 72
　　96 32
　　97 96
　　98 42
　　99 60
　　100 40

晚上七点到八点花了不到一个小时写出来的表达式求值程序，因为几个无语的错误，居然调试到现在，累计调试的时间大概有五个小时了吧，太打击自信了！

教训：写代码细心，实时检验，以免程序长了之后花数倍的时间调试

#include<stack>
//#include<string>
#include<iostream>

using namespace std;

short Com[7][7]={ {1,1,0,0,0,1,1},{1,1,0,0,0,1,1},//运算符优先级
    {1,1,1,1,0,1,1},{1,1,1,1,0,1,1},
    {0,0,0,0,0,2,1},{1,1,1,1,1,1,1},{0,0,0,0,0,0,0}};
   
int Operate(int a,char theta,int b)//计算
{
if(theta=='+')return a+b;
if(theta=='-')return a-b;
if(theta=='*')return a*b;
if(theta=='/')return a/b;
}
int StoN(char z)//返回操作符代号便于计算优先级
{ if(z=='+')return 0;
if(z=='-')return 1;
if(z=='*')return 2;
if(z=='/')return 3;
if(z=='(')return 4;
if(z==')')return 5;
if(z=='#')return 6;
}

int count(char s[])//主程序
{
stack<char> oper;
stack<int> num;
int aa,bb,cc,t,ccc;
oper.push('#');
int l=strlen(s),i,j;
char temp[]="#";
strcat(s,temp);
//s[l+1]=35;
char c,theta;
i=-1;
c=s[++i];
while(c!='#' || oper.top()!='#')//oper.top()!='#'
{
   //if(!(c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')'))
   if(c>='0' && c<='9')
   {
    t=0;
    while(c>='0'&&c<='9')
    {
     t++;
     c=s[++i];
    }
    int d=atoi(s+i-t);
    i--;
    num.push(d);
    c=s[++i];
   }
   else
   {
    cc=StoN(oper.top());
    ccc=StoN(c);
    //oper.pop;
    switch(Com[cc][ccc])
    {
     case 0:// <
      oper.push(c);
      c=s[++i];
      break;
     case 2:// =
      oper.pop();
      c=s[++i];
      break;
     case 1:// >
      theta=oper.top();
      oper.pop();
     
      bb=num.top();
      num.pop();
     
      aa=num.top();
      num.pop();
     
      num.push(Operate(aa,theta,bb));
      break;
    }
   }
}
return num.top();
}

int main()
{
int n,base;
char s[100];
while(1){
cout<<"输入表达式";
cin>>s;
cout<<"key="<<count(s)<<endl;
}


printf("\n");
system("pause");
}
//4+2*3-10/5 ac
//2+(3+4/2)*2 ac
//2*(3+4/2)*2 ac
//2*2+(3+4) ac
//1+(2+3) ac

ps：百度不支持tab，晕。。。

速度水一下，不解释。

1.AC902队有三人，都是菜鸟

2.ltj_njust说刚开学，状态不好，没参加

3.nosh来了，看了一会儿，分工做了倒数第三题，做了一个小时后困了，然后回去睡觉了

4.我分工先做倒数第二题，调了一个小时许，未果，孤立无援，遂放弃

5.明天正式开学，我要好好调整状态，收心！

参加的是Codeforces Beta Round #26

毕竟第一次嘛，加上自己本来就实力不济，所以比赛心态不错，洗完澡都11点多了才开始，一点都不着急。

第一题，找恰有两个不同质因数的数字个数，不难，我比较猥琐，搞了一个1-3000的质数表，代码长度3k

第二题，去掉一些括号，找出能全部配对的最大长度，一开始我受到校赛影响，看错题，交了完全错误的代码，居然通过了机器测试，后来在0：45被hack了，时间所剩无几，我就不想改了

第三题觉得太麻烦，第四题写一阵系统提示第二题被hack了，发现是自己严重看错题后愤而放弃比赛！

第一次经历就这样啦，教训：

1。仔细看题，这次是狠狠被熟题坑了

2。熟悉编译环境，今天一共三次编译错误。。。

在初学一门编程语言的时候，写一个“Hello world!”程序是最常见的入门方法。通过写一个成功的“Hello world!”，可以实践这门语言最基本的语法特性，还可以带给自己成就感，真是一举两得。C/C++语言本身有很多特性，如果能够将这些技术分解出来变成一个个的“Hello world!”，并且将这些技术点到为止，貌似也算是一件善事。这里，列举了10个“Hello world!”程序，大家雅俗共赏一下。

1. 最经典的“Hello world!”
“Hello world!”最经典的写法当然是直接用 printf 输出“Hello world!”这几个字符了。无论用C还是 C++，写起来都非常的简洁明了。这里把最常见的几个全部列在下面。

#include <stdio.h>
#include <iostream>

int main()
{
    printf("Hello world!");                   // 教科书的写法
    puts("Hello world!");                     // 我最喜欢的
    puts("Hello" " " "world!");               // 拼接字符串
    std::cout << "Hello world!" << std::endl; // C++风格的教科书写法

    return 0;
}
特别需要注意的是，在C/C++里，如果两个字符串之间除空白符以外没有任何东西，编译器会自动认为这两个字符串是连在一起的字符串。这样，如果一个字符串过长，可以用这种方法换行来写，既不浪费性能，又美观。

2. 用宏写的“Hello world!”
在C/C++里，宏是一个神奇的东西。特别是在C语言中，宏可以帮我们做一些“又脏又累”的活，包括拼接代码片断、隐藏繁琐的实现细节等等。其中特别有趣的是“#”的用法，它可以“提取”参数的名字，把它变成字符串。
#include <stdio.h>

#define Say(sth) puts(#sth)

int main()
{
    return Say(Hello world!);
}
请注意，这个Hello world可是完全没有出现引号哦！

3. 断章取义的“Hello world!”
字符串是一种常量这当然毫无疑问，但是它的类型是什么，这就需要考虑一下了。使用C++的typeid就可以这个问题的答案，而且只要是符合C或C++标准的编译器就应该是一样的结果。比如字符串“Hello world!”，它的类型就是 char const [13]。
知道了这个，就可以写出以下的“Hello world!”：
#include <stdio.h>

int main()
{
    return puts(&"Do not say: Hello world!"[12]);
}

4. 退出时运行的“Hello world!”
大家都知道 main 函数退出意味着程序结束，可是这并不完全正确，我们完全可以在 main 函数退出以后做很多事呢——比如说，输出“Hello world!”。这个功能依赖于C标准库中提供的函数 atexit()，调用这个函数并注册自己的回调函数就行。需要注意，这个函数可以调用多次，最后注册的函数最先执行。
#include <stdio.h>
#include <stdlib.h>

void say()
{
    printf("world!");
}

void sth()
{
    printf("Hello ");
}

int main()
{
    return atexit(say), atexit(sth);
}

5. 读取自己的“Hello world!”
C/C++的编译器提供了一些有用的内置宏，最常用的就是 __FILE__ 和 __LINE__ 了。其中，__FILE__ 代表当前的源文件的文件名，嗯，对了，如果我们让这个程序读取自己的源文件，不就可以做一个很有意思的“Hello world!”了么？
// Hello world!

#include <iostream>
#include <fstream>
#include <string>

int main()
{
    std::ifstream ifs(__FILE__);
    std::string say, some, word;

    ifs >> say >> some >> word;
    std::cout << some << " " << word;

    return 0;
}

6. 话分两头的“Hello world!”
有了C++的类，我们就可以光明正大的在 main 函数执行之前和之后做感兴趣的事情了。我们可以声明一个全局的类的实例，这样，在 main 函数执行之前会调用这个类的构造函数，结束之后则会调用析构函数。
#include <iostream>

class say
{
public:
    say()
    {
        std::cout << "Hell";
    }

    ~say()
    {
        std::cout << "world!";
    }
}hello;

int main()
{
    std::cout << "o ";
    return 0;
}

7. 传入模板的“Hello world!”
C++的模板功能极为强大，可以说是C++里面最艰深、最经典、最时尚的部分。一个“Hello world!”当然无法使用很多很高级的模板技巧，我也不想只使用模板特化这样无阻挂齿的小技巧，嗯，那就来演示一个比较罕见的用法吧。
#include <iostream>

template <char * words>
class say
{
public:
    void operator () ()
    {
        std::cout << words;
    }
};

extern char hello[] = "Hello world!";

int main()
{
    return say<hello>()(), 0;
}
请注意，这个 extern 是十分必要的，只有加上了 extern，这个指针才是一个编译器间可以确定的值，也才可以参与模板运算。还有，hello 必须为数组类型，而不能为 char*，这个道理和加 extern 是一样的。
此外，这里还演示了 functor 的用法，嗯，关于它的优点就不在这里多说了，反正是与原生指针相比有很多好处就是了。

8. 调用私有函数的“Hello world!”
我们知道，C++类的私有函数是不能被外界访问的，比如说 main 函数里面，它绝对不能访问类的私有函数，除非把它设为类的友元函数。不过我们还是可以用一些比较奇怪的方法访问类的私有函数——当然，这个私有函数必须满足一个条件：它是虚函数。
这里就涉及到一个问题，指向虚函数的虚表放在哪里？对于 VS.Net 2003 而言，虚表是类的第一个成员，虚函数指针按照函数声明的顺序放在虚表里面。当然，这个说法并不严谨，更细节的东西还是去看看那本“成人高钙奶粉”吧，它会给出最权威的解答。
这里是一个很有意思的例子：
#include <iostream>
#include <cstddef>

class secret
{
private:
    virtual void say()
    {
        std::cout << "Hello world!";
    }
};

int main()
{
    secret word;
    (reinterpret_cast<void (*)()>(**(intptr_t**)(&word)))();

    return 0;
}

9. 最暴力的“Hello world!”
最暴力的调用函数的方法是：直接修改函数的返回地址，让这个地址指向我们想要调用的函数。这也就是缓冲区溢出漏洞的应用方法了，不过里面还涉及到很多问题，在这里就不一一列举，想要了解的话，还是去 Google 吧。这里只演示一个可以在 VS.Net 2003 下可以用的“Hello world!”。
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>

void say()
{
    puts("Hello world!");
    exit(0);
}

int main()
{
    volatile intptr_t a = 0;
    volatile intptr_t * p = &a;

    *(p + 2) = (intptr_t)say;
    *(p + 3) = (intptr_t)say;

    return 0;
}

10. 外星人说的“Hello world!”
好了，这个“Hello world!”是最匪夷所思的一个了！不过它并没有涉及任何复杂的C/C++语言特性，只是看起来有点酷。你能看懂外星人在说什么不？
#include <stdio.h>

void alien_say(char * p)
{
    while (putchar(*(p += *(p + 1) - *p)));
}

int main()
{
    return alien_say("BETHO! Altec oh liryom(a loadjudas!) dowd."), 0;
}