首页 > ACM题库 > HDU-杭电 > HDU 3508-Product of coprimes[解题报告]HOJ
2014
04-09

HDU 3508-Product of coprimes[解题报告]HOJ

Product of coprimes

问题描述 :

You are given a positive integer m. Calculate the product of all positive integers less then or equal to m and coprime with m, and give the answer modulo m.

输入:

There are multiple tests end with EOF, each test contains only a positive integer m ≤ 10^9 in a line. The number of tests is no more than 5000.

输出:

There are multiple tests end with EOF, each test contains only a positive integer m ≤ 10^9 in a line. The number of tests is no more than 5000.

样例输入:

1
2
3
4
5
6
7

样例输出:

0
1
2
3
4
5
6

#include<cstdio>
#include<vector>

#define MAXX 32000

int i,j,m,n;
std::vector<int>prm;
bool flag[MAXX];

int main()
{
 prm.reserve(MAXX);
 for(i=2;i<MAXX;++i)
 {
 if(!flag[i])
 prm.push_back(i);
 for(j=0;j<prm.size() && i*prm[j]<MAXX;++j)
 {
 flag[i*prm[j]]=true;
 if(i%prm[j]==0)
 break;
 }
 }
 while(scanf("%d",&m)!=EOF)
 {
 if(!m)
 {
 puts("0");
 continue;
 }
 if(m<8)
 {
 printf("%d\n",m-1);
 continue;
 }
 n=m;
 if(!(m&1))
 {
 m>>=1;
 if(!(m&1))
 {
 puts("1");
 continue;
 }
 }
 for(i=1;i<prm.size();++i)
 if(m%prm[i]==0)
 {
 do
 m/=prm[i];
 while(m%prm[i]==0);
 break;
 }
 if(m==1 || i>=prm.size())
 printf("%d\n",n-1);
 else
 puts("1");
 }
 return 0;
}

  1. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。