主题:help!
找新朋友
--------------------------------------------------------------------------------
Time limit: 1000MS Memory limit: 32768K
--------------------------------------------------------------------------------
新年快到了,“猪头帮协会”准备搞一个聚会,已经知道现有会员N人,把会员从1到N编号,其中会长的号码是N号,凡是和会长是老朋友的,那么该会员的号码肯定和N有大于1的公约数,否则都是新朋友,现在会长想知道究竟有几个新朋友?请你编程序帮会长计算出来。
输入:第一行是测试数据的组数CN(Case number,1<cn<10000),接着有CN行正整数N(1<n<32768),表示会员人数。
输出:对于每一个N,输出一行新朋友的人数,这样共有CN行输出。
Sample input:
2
25608
24027
Sample output:
7680
16016
我是这样写的
#include <iostream>
using namespace std;
//交换a ,b的值
void swap(int& a1,int &b1)
{
int temp;
temp=a1;
a1=b1;
b1=temp;
}
//移位相减法
int gcd2(int a,int b)
{
if(a < b)swap(a,b);
if(a==0)return b;
if(b==0)return a;
while(a != b)
{
if(( (a&1) == 0 ) && ( (b&1) == 0 )){
return 2*gcd2(a/2,b/2);
}else if(( (a&1) == 1 ) && ( (b&1) == 0)){
return gcd2(a,b/2);
}else if(((a&1) == 0 ) && ( (b&1) == 1) ){
return gcd2(a/2,b);
}else if(((a&1) == 1 ) && ((b&1) == 1)){
return gcd2(b,(a-b));
}
}
return b;
}
int main()
{
int cn,i,n,m,k;
while(cin>>cn)
{
while(cn--)
{
cin>>m;
n=m-1;
k=0;
for(i=0;i<=n;i++)
{
if(gcd2(m,i)>1)
k++;
}
cout<<m-k<<endl;
}
}
return 0;
}
时间超出了限制>1000MS了
问这样改进或者怎么样写才能TIME<1000MS
--------------------------------------------------------------------------------
Time limit: 1000MS Memory limit: 32768K
--------------------------------------------------------------------------------
新年快到了,“猪头帮协会”准备搞一个聚会,已经知道现有会员N人,把会员从1到N编号,其中会长的号码是N号,凡是和会长是老朋友的,那么该会员的号码肯定和N有大于1的公约数,否则都是新朋友,现在会长想知道究竟有几个新朋友?请你编程序帮会长计算出来。
输入:第一行是测试数据的组数CN(Case number,1<cn<10000),接着有CN行正整数N(1<n<32768),表示会员人数。
输出:对于每一个N,输出一行新朋友的人数,这样共有CN行输出。
Sample input:
2
25608
24027
Sample output:
7680
16016
我是这样写的
#include <iostream>
using namespace std;
//交换a ,b的值
void swap(int& a1,int &b1)
{
int temp;
temp=a1;
a1=b1;
b1=temp;
}
//移位相减法
int gcd2(int a,int b)
{
if(a < b)swap(a,b);
if(a==0)return b;
if(b==0)return a;
while(a != b)
{
if(( (a&1) == 0 ) && ( (b&1) == 0 )){
return 2*gcd2(a/2,b/2);
}else if(( (a&1) == 1 ) && ( (b&1) == 0)){
return gcd2(a,b/2);
}else if(((a&1) == 0 ) && ( (b&1) == 1) ){
return gcd2(a/2,b);
}else if(((a&1) == 1 ) && ((b&1) == 1)){
return gcd2(b,(a-b));
}
}
return b;
}
int main()
{
int cn,i,n,m,k;
while(cin>>cn)
{
while(cn--)
{
cin>>m;
n=m-1;
k=0;
for(i=0;i<=n;i++)
{
if(gcd2(m,i)>1)
k++;
}
cout<<m-k<<endl;
}
}
return 0;
}
时间超出了限制>1000MS了
问这样改进或者怎么样写才能TIME<1000MS