#include <stdio.h>
#include <math.h>

int a[30];

void seta(int a[], int m){
    int i, j;
	a[0]=0; j=1;
	for( i=2; m>1 ; ){
		if(m%i!=0) i++;
		else if(m%i==0){
			m=m/i;
			if(i!=a[j-1]){
				a[j++]=i;
				a[0]++;
			}
		}
	}
}

int main(){
	int m, k, r, res, i, j;
	while(scanf("%d%d", &m, &k)==2){
		if(m==1){
			printf("%d\n", k);
			continue;
		}
		seta(a, m);
		r=m;
		for(i=1; i<=a[0]; i++){
			r=r*(a[i]-1)/a[i];
		}
		res=k/r*m;
		k=k%r; 
        if(k==0) res--;
		for(i=1; k>0; i++){
			for(j=1; a[j]<=i && j<=a[0]; j++){
				if(i%a[j]==0) goto L;
			}
			k--;
L:;
		}
		i--;
		res+=i;
		printf("%d\n", res);
	}
	return 0; 
}

• 用 欧拉函数， 然后枚举， 但是我按解题报告这么做的怎么那么慢 (781) semonteer 2006-03-26 23:29:09
  • 这样我就做到31ms (0) xiaxia 2006-03-26 23:30:05
    • 高手 mail 给 我学习一下吧， 我太菜了 (0) semonteer 2006-03-26 23:31:45
      • 我要是高手就没有低手了 (0) xiaxia 2006-03-26 23:32:35
      • Re:高手 mail 给 我学习一下吧， 我太菜了 (956) first 2006-03-26 23:35:15
        • ！！！！！ (1064) frkstyc 2006-03-26 23:36:10
  • 太好了有解体报告 (0) xiaxia 2006-03-26 23:30:52
    • Re:太好了有解体报告 (13) 350053879 2006-03-29 18:30:27
      • 题目下边 (17) FinalPhase 2006-03-29 18:46:19
  • 用sieving吧做起来简单 (0) frkstyc 2006-03-26 23:31:04
    • 我一直超时....大哥们能不能发我一份代码啊？ (0) Sempr 2006-03-26 23:33:25
      • Re:我一直超时....大哥们能不能发我一份代码啊？ (956) first 2006-03-26 23:34:45
        • 不要公开发！ (1064) frkstyc 2006-03-26 23:35:33
          • 你帮我删掉啊 (0) first 2006-03-26 23:36:04
        • 能不能删掉啊，我mail弄错了 (1064) first 2006-03-26 23:35:48
• 谢谢frkstyc大哥和first大哥(PS:frkstyc大哥不喜欢别人叫大牛，那就叫大哥吧) (0) Sempr 2006-03-26 23:46:32
  • 叫st就好了:) (0) xfxyjwf 2006-03-26 23:52:39
    • ^_^ (0) Sempr 2006-03-26 23:56:59
    • 有些东西的确是没有必要…… (0) frkstyc 2006-03-27 04:52:31