POJ 2773 Happy 2006 数学题 - c++编程基础

因为k可能大于m,利用gcd(m+k,m)=gcd(k,m)=gcd(m,k)的性质,最后可以转化为计算在[1,m]范围内的个数t。

1、AC代码：

开始的时候从1开始枚举if(gcd(n,i)==1)，果断跑了2000ms

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef __int64 LL;
const int N=1000002;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

inline int in()
{
char ch = getchar();
int data = 0;
while (ch < '0' || ch > '9')
{
ch = getchar();
}
do
{
data=data*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return data;
}

int xh[N];

int gcd(int n,int m)
{
int t;
while(m)
{
t=n%m;
n=m;
m=t;
}
return n;
}

int main()
{
int i,j,n,k;
xh[1]=1;
while(cin>>n>>k)
{
if(n==1)
{
printf("%d\n",k);
continue;
}
int x=1;
for(i=2;i {
if(gcd(n,i)==1)
xh[++x]=i;
}
int t=k%x,p=(k-1)/x;
if(t==0)
t=x;
printf("%d\n",p*n+xh[t]);
}
return 0;
}

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef __int64 LL;
const int N=1000002;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

inline int in()
{
char ch = getchar();
int data = 0;
while (ch < '0' || ch > '9')
{
ch = getchar();
}
do
{
data=data*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return data;
}

int xh[N];

int gcd(int n,int m)
{
int t;
while(m)
{
t=n%m;
n=m;
m=t;
}
return n;
}

int main()
{
int i,j,n,k;
xh[1]=1;
while(cin>>n>>k)
{
if(n==1)
{
printf("%d\n",k);
continue;
}
int x=1;
for(i=2;i {
if(gcd(n,i)==1)
xh[++x]=i;
}
int t=k%x,p=(k-1)/x;
if(t==0)
t=x;
printf("%d\n",p*n+xh[t]);
}
return 0;
}

2、AC代码

将于m互质的数记录下来。

[cpp]
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

typedef __int64 LL;
const int N=1000002;
const LL II=1000000007;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

inline int in()
{
char ch = getchar();
int data = 0;
while (ch < '0' || ch > '9')
{
ch = getchar();
}
do
{
data=data*10+ch-'0';
ch=getchar();
}while(ch>='0'&&ch<='9');
return data;
}

int xh[N];
LL pri[N],x;
bool vis[N];

void prime()//求素数
{
LL i,j;
x=0;
memset(vis,false,sizeof(vis));
for(i=2;i {
if(!vis[i])
pri[++x]=i;
for(j=1;j<=x&&pri[j]*i {
vis[pri[j]*i]=true;
if(i%pri[j]==0)
break;
}
}
}

int main()
{
LL n,k,i,j;
prime();
while(scanf("%I64d%I64d",&n,&k)!=EOF)
{
LL q=n,sum=n;
if(n==1)
{
printf("%I64d\n",k);
continue;

POJ 2773 Happy 2006 数学题 (一)