PKU 2649. Factovisors. TLE네요...

으으 결국 받지 못했습니다...AC...
저는 2개 코드를 짰는데요...
처음은 링크드리스트를 이용한 코드입니다...
#include<stdio.h> #include<stdlib.h> typedef struct pnode{ int data; int count; struct pnode *next; }NODE; NODE *insert(NODE *p,int num) { NODE *temp,*curr,*prev; curr=p; prev=NULL; if(p==NULL){ p=(NODE *)malloc(sizeof(NODE)); p->data=num; p->count=0; p->count=p->count+1; p->next=NULL; return p; } else{ if(curr->data > num){ temp = (NODE *)malloc(sizeof(NODE)); temp->data=num; temp->count=0; temp->count=temp->count+1; temp->next=curr; p=temp; return p; } while (curr->data < num){ if(curr->next==NULL){ temp = (NODE *)malloc(sizeof(NODE)); temp->data=num; temp->count=0; temp->count=temp->count+1; temp->next=NULL; curr->next=temp; return p; } prev = curr; curr = curr->next; } if(curr->data == num){ curr->count=curr->count+1; return p; } temp = (NODE *)malloc(sizeof(NODE)); temp->data=num; temp->count=temp->count+1; temp->count=1; temp->next=curr; prev->next=temp; return p; } } NODE *prfa(NODE *p,int n){ int divcou=2; while(n != 1){ while((n%divcou == 0) && (n != 1)){ n=n/divcou; p=insert(p,divcou); } divcou++; } return p; } int compa(NODE *p,NODE *q) { while(p!=NULL && q!=NULL){ if(p->data==q->data){ if((p->count-q->count) >= 0){ p=p->next; q=q->next; } else return 1; } else if(p->data > q->data) return 1; else if(p->data<q->data) p=p->next; } if(p==NULL && q!=NULL) return 1; return 0; } int main(void) { NODE *head,*mpac; int n,m,i,result; while(scanf("%d%d",&n,&m)!=EOF){ head=NULL; mpac=NULL; if(n >= m) result=0; head=prfa(head,m); for(i=1;i<=n;i++) mpac=prfa(mpac,i); result=compa(mpac,head); if(result==0) printf("%d divides %d!\n",m,n); else printf("%d does not divide %d!\n",m,n); } return 0; } 예...그렇습니다...깁니다...시간따위 잊었습니다...으으
링크드리스트 포스트 하는김에 한번 짜봤었습니다...당연하게 TLE가 나는거죠...

사실 이 긴코딩중의 반이 노드 추가함수였습니다...
N!의 모든 소인수를 링크드리스트로 연결해서 같은것은 카운트를 올리고...M도 마찬가지로 했습니다...
그리고 카운트된 소인수의 갯수들을 빼서 M의 소인수를 모두 못 없애면 못 나누는 것이지요...
예...컴퓨터씨가 화내더군요...N!이 커지니까 시간은 안드로메다로 떠나더군요...

음 그래서 다시짜봤습니다...

#include<stdio.h> int gcd(int x, int y) { int temp; temp = x % y; if (temp == 0) return y; else return gcd(y, temp); } int main(void){ int m,n,i,temp; while(scanf("%d%d",&n,&m) != EOF){ temp=m; for(i=1;(i<=n)&&(temp != 1);++i) temp=temp/gcd(temp,i); if(temp==1) printf("%d divides %d!\n",m,n); else printf("%d does not divide %d!\n",m,n); } return 0; } 이야 아까에 비하면 확실이 줄었죠...
이번건 최대공약수로 나눠가면서 1이 되면 모두 나누어 떨어진다고 파악하도록 했습니다...
그런데 이것도 TLE더군요...

이거 가지고 다시 수정해봐야겠습니다...