항 전 "컴퓨터 대학 대학생 프로 그래 밍 경기 (2015 '11)" 문제 풀이 [4 - 6]

1004 제곱 수
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3521 Accepted Submission(s): 1183
Problem Description 샤 오 밍 은 천성적으로 숫자 에 민감 해 3 살 때 원주율 100 위 를 외 울 수 있다.
현재 샤 오 밍 은 점점 자 랐 지만 여전히 숫자 를 좋아한다. 최근 에 그 는 질 수 와 제곱 수 에 빠 졌 고 자신 은 질 수의 제곱 을 '질 방 수' 라 고 명명 했다.현재 그 는 이러한 문 제 를 연구 하고 있다. 정수 N 에서 가장 가 까 운 질 방 수 는 얼마 입 니까?
Input 입력 데이터 의 첫 줄 은 T 조 입력 데이터 가 있 음 을 나타 내 는 정수 T (T < = 20) 이다.다음 T 줄 은 줄 마다 정수 N (1 < = N < = 10 ^ 8) 을 입력 합 니 다.
출력 은 각 그룹의 데이터 에 대해 N 에서 가장 가 까 운 질 방 수 를 출력 하 십시오. 각 그룹의 출력 은 한 줄 을 차지 합 니 다.
Sample Input
2 1 10
Sample Output
4 9
제목 과 뜻 을 개술 하 다.
주어진 n 에서 가장 가 까 운 질량 방 수 를 찾 습 니 다.
제목 분석
n, m 를 소수 로 가정 하고 n
코드

#include
#include
using namespace std;

#define Max 10000
int a[Max+1]={1,1,0};

int main(){
    for( int i=2; i<=5000; i++ )
        for( int j=i<<1; j1; j+=i ){
               a[j]=1;
        }
    int T;
    int N;
    cin>>T;
    while( T-- ){
        cin>>N;
        int temp=sqrt(N);
        if( temp*temp == N && a[temp]==0 )
            cout<else if( temp==1 )
            cout<<4<else{
                int i, j;
                for( i=temp; i>=2; i-- ){
                if( a[i]==0 )
                    break;
            }
            for( j=temp+1; j<=Max; j++ ){
                if( a[j]==0 )
                    break;
            }
            if( N-i*i <= j*j-N )
                cout<else
                cout<

1005 ACM 팀 구성
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 928 Accepted Submission(s): 437
Problem Description ACM 아시아 지역 경기 가 끝 난 것 은 내년 절강성 대학생 프로 그래 밍 경 기 를 준비 하 는 것 을 의미 합 니 다!항 저 우 전자 과 기대 학 ACM 합숙 훈련 대도 팀 구성 을 시작 할 준 비 를 하고 있다.감독 은 모든 n 명의 선 수 를 몇 개의 팀 으로 구성 하려 고 하 는데, 원칙 은 각 팀 이 적어도 한 명, 최대 세 명 이 어야 한 다 는 것 이다.지금 문제 가 생 겼 습 니 다. 합숙 팀 선수 의 수 n 을 알 고 있다 면 가능 한 모든 팀 구성 방안 이 몇 가지 인지 계산 해 주세요.
특히 팀 에 번호 가 없습니다. 즉, A, B, C 세 명 이 있 으 면 {A} {BC} 과 {BC} {A} 은 같은 팀 의 상황 입 니 다.
Input 입력 은 여러 조 의 테스트 데이터 (약 1000 조) 를 포함 하고 각 조 의 데 이 터 는 한 줄 을 차지 하 며 하나의 숫자 n (0 < = n < 20) 을 포함 하여 ACM 합숙 훈련 팀 의 대원 수 를 나타 낸다.n 은 0 으로 입력 이 끝 났 음 을 나타 낸다.
출력 n 개 대원 의 모든 가능 한 파티 방안 수 를 출력 하 십시오. 각 그룹의 출력 은 한 줄 을 차지 합 니 다.
Sample Input
1 2 3 4 5 0
Sample Output
1 2 5 14 46
제목 과 뜻 을 개술 하 다.
n 명 을 정 하여 모든 팀 의 가능 수 를 구하 세 요 (그 중 1 인 1 팀, 2 인 1 팀, 3 인 1 팀)
제목 분석
d [n] 를 n 개인 팀 으로 설정 하 는 모든 가능 한 m 번 째 팀 의 구성 방식 은 다음 과 같은 몇 가지 가 있다. 1 인 1 팀: 모두 d [m - 1] 방식 과 다른 1 인 팀: 모두 d [m - 2] C (n - 1), 1) = d [m - 2] * (n - 1) 방식 과 다른 2 인 팀: 모두 d [m - 3] C ((n - 1), 2) = d [m - 2] (n - 2) (n - 2) / 2 그래서 d[m]=d[m-1]+d[m-2]*(n-1)+d[m-2]*(n-1)*(n-2)/2코드

#include
#include
#include
#include
#include
#include
using namespace std;
#define N 1005
int main(){
    int n;
    long long f[N]={0,1,2,5};
    for(int i=4;i<=20;i++){
        f[i]=f[i-1]+(i-1)*f[i-2]+f[i-3]*(i-1)*(i-2)/2;
    }
    while(scanf("%d",&n),n){
        printf("%lld
",f[n]);
    }
    return 0;
}

1006 역습 지수
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1629 Accepted Submission(s): 314
Problem Description 이것 은 여전히 고부 수 샤 오 밍 에 관 한 이야기 입 니 다.
역경 에 도 불구 하고 샤 오 밍 은 노력 을 포기 하지 않 았 다. 벽돌 을 옮 기 는 것 외 에 샤 오 밍 은 동양 의 팔괘 와 서양의 별 자 리 를 연구 하여 자신 이 역습 할 수 있 는 근 거 를 명리 적 으로 찾 으 려 고 노력 해 왔 다.
이런 것들 이 모두 실패 한 후에 샤 오 밍 은 수학 연구 로 전향 하여 그 중에서 약간의 정 보 를 얻 기 를 희망 했다.어느 날 샤 오 밍 은 이라는 책 을 연구 할 때 소중 한 정 보 를 발견 했다. 그 중에서 모든 사람 에 게 역습 지수 가 존재 하 는데 이 역습 지수 에 대해 연속 적 인 인자 가 존재 할 수 있다. 만약 에 이 연속 인자 가 충분 하 다 면 이 사람 이 역습 할 확률 이 매우 크다!
샤 오 밍 은 자신의 역습 지 수 를 알 고 있 으 니 샤 오 밍 에 게 가장 긴 연속 요 소 를 알려 자신 이 역습 할 수 있 는 지 없 는 지 를 판단 하 게 해 주세요.
Input 입력 은 여러 그룹의 테스트 데 이 터 를 포함 합 니 다.각 조 의 데 이 터 는 한 줄 을 차지 하고 하나의 정수 N 을 포함 하 며 샤 오 밍 의 역습 지 수 를 나타 내 며 N 은 2 ^ 31 보다 작다.
출력 은 각 그룹의 데이터 에 대해 2 줄 을 출력 하 십시오. 첫 번 째 줄 에서 가장 긴 인자 개 수 를 출력 하 십시오.두 번 째 줄 의 출력 최소 인자 서열 은 구체 적 으로 사례 를 참고 하 시기 바 랍 니 다.
특히 샤 오 밍 은 싱글 을 싫어 하기 때문에 1 은 인자 가 아니다.
Sample Input
630 12
Sample Output
3 5*6*7 2 2*3
Hint
630 = 3*5*6*7
제목 분석
n 구 n 의 최 장 연속 인자 (1 제외) 길 이 를 정 하고 (여러 개 있 으 면 첫 번 째 로 가장 작은 것 을 취하 고) 곱 하기 n 인자 입 니 다.
제목 분석
폭력 구 해 는 n 의 모든 가능 한 인자 (2. sqrt (n) 를 옮 겨 다 니 며 가장 긴 연속 요 소 를 찾 습 니 다.
코드

#include 
#include 
#include 
#include 
using namespace std;
int main()
{
    //cout<
    long long  m;
    while(~scanf("%d",&m)){
        long long mult=1;
        long long sum=0;
        long long last = 0;
        long long tempSum = 0;
        long long orig = m;
        for(long long j=2;j*j<=m;j++){
            for(long long i=j;i<=m;i++){
                if(orig%i==0){//   
                    mult*=i;
                    if(orig%mult==0){//     
                        tempSum++;
                        if(tempSum>sum){//  
                            sum=tempSum;
                            last = i;
                        }
                    }else{//       init
                        tempSum = 0;
                        mult = 1;
                        break;
                    }
                }else{//    
                    tempSum = 0;
                    mult = 1;
                    break;
                }
            }
        }
        if(sum==0){
            printf("1
%d
",orig);
        }else{
            printf("%d
",sum);
            for(long long i = sum-1;i>=1;i--){
                printf("%d*",last-i);
            }
            printf("%d
",last);
        }
    }
    return 0;
}