문제
#include <stdio.h> #define MAX 1000000
int arr[ MAX+1 ] = {0};
int main() { int i; int n,m,r;
scanf("%d %d", &n,&m); for( i = 1 ; i <= MAX ; i++ ) { if(n%i == 0)arr[i]++; if(m%i == 0)arr[i]++; } for(i = 1 ; i<=MAX; i++ ) { if(arr[i]>=2) r = i; } if( r==1 ) printf("Wow\n"); else printf("Not Wow\n"); return 0; } |
MAX = 1000000 arr = [0 for i in range(MAX+1)]
n,m = input().split() n,m = int(n),int(m)
for i in range(1,MAX+1): if n%i == 0 : arr[i]+=1 if m%i == 0 : arr[i]+=1
for i in range(1,MAX+1): if arr[i]>=2 : r=i
if r==1: print("Wow") else: print("Not Wow")
|
이 프로그램은 두 정수 n, m이 공백을 사이에 두고 주어지면, Wow 또는 Not Wow중 한가지 문장을 출력한다.
호중이는 어떤 정수 n과 k가 주어졌을 때, 1≤m≤k를 만족하는 모든 정수 m에 대해서, n과 m을 위 프로그램의 입력으로 넣었을 때의 출력 결과가 Wow인 경우가 총 몇 가지나 있나 세어보려고 한다.
예를 들어, n=3, k=6이라면 m=1, 2, 4, 5일 때 Wow를 출력하고, 나머지 경우에는 Not Wow를 출력하므로, Wow를 출력하는 경우의 수는 총 4가지가 된다.
이처럼 정수 n과 k가 주어졌을 때, 위 프로그램에 [n m]을 입력해서 Wow가 나오는 k이하의 m의 개수를 세어주는 프로그램을 작성하라.
입력
첫 줄에 두 정수 n과 k가 공백을 사이에 두고 주어진다.
부분문제의 제약 형식
모든 입력값은 정수이며, 1≤n,k≤106(100만)이다.
부분문제 1)( 6점)n=1이다.
부분문제 2)(15점)k≤10이다.
부분문제 3)( 9점)n은 소수(prime number)이다.
부분문제 4)(70점)주어진 제약조건 외에 아무 제약조건이 없다.
출력
k이하의 모든 정수 m에 대해서, 지환이나 시후가 쓴 코드에 n m을 입력했을 때 Wow가 출력되는 경우의 수를 출력한다.
예제
3 6
4
로그인해야 코드를 작성할 수 있어요.