跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0524. Problem E: Relatives

  • ID: 530
  • 传统题
  • 1000ms
  • 128MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:待分级
  • 上传者:
  • 待分类
  • 整理状态
  • 难度待定
  • 难度
  • 共享题库
  • 高校与竞赛共享题
  • 英文题面
  • 题目来源
  • 题面语言

Problem E: Relatives

题目描述

Problem E: Relatives

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.

There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.

For each test case there should be single line of output answering the question posed above.

样例 1

输入

7
12
0

输出

6
4

题目来源:fps-zhblue-waterloo-020601.xml;FPS 共享题包,题包内第 5 题。保留原作者与原赛事署名。