hdoj 1999 만 질 수 없 는 숫자 [수학 적 인자 와]

헤 아 릴 수 없다
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10552 Accepted Submission(s): 2724
Problem Description
s (n) 는 정수 n 의 진짜 인자 의 합, 즉 n 보다 작고 n 을 제거 하 는 인자 와. 예 를 들 어 s (12) = 1 + 2 + 3 + 4 + 6 = 16. 만약 에 그 어떠한 것 도
m, s (m) 는 모두 n 과 같 지 않 으 면 n 을 만 질 수 없 는 숫자 라 고 부른다.

Input
여러 그룹의 데 이 터 를 포함 하여 먼저 T 를 입력 하면 T 그룹의 데이터 가 있 음 을 나타 낸다. 각 그룹의 데이터 1 줄 은 n (2 < = n < = 1000) 을 정수 로 한다.

Output
n 이 만 질 수 없 는 숫자 라면 yes 를 출력 합 니 다. 그렇지 않 으 면 no 를 출력 합 니 다.

Sample Input

 
   
     3 2 5 8

Sample Output

 
   
     yes yes no

一开始只想着找规律，WA两次后放弃了。直接暴力打表。。。

打到1000*1000就够用了。用筛选法求因子和。

AC代码:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define INF 0x3f3f3f
#define eps 1e-8
#define MAXN (1000000+1)
#define MAXM (100000)
#define Ri(a) scanf("%d", &a)
#define Rl(a) scanf("%lld", &a)
#define Rf(a) scanf("%lf", &a)
#define Rs(a) scanf("%s", a)
#define Pi(a) printf("%d
", (a))
#define Pf(a) printf("%.2lf
", (a))
#define Pl(a) printf("%lld
", (a))
#define Ps(a) printf("%s
", (a))
#define W(a) while(a--)
#define CLR(a, b) memset(a, (b), sizeof(a))
#define MOD 1000000007
#define LL long long
#define lson o<<1, l, mid
#define rson o<<1|1, mid+1, r
#define ll o<<1
#define rr o<<1|1
using namespace std;
map fp;
int sum[MAXN];
void get()
{
    for(int i = 1; i <= 1000000; i++)
    {
        if(i == 1)
            sum[i] = 1;
        else
            sum[i] = i + 1;
    }
    for(int i = 2; i*i <= 1000000; i++)
    {
        for(int j = i; i*j <= 1000000; j++)
        {
            if(i == j)
                sum[i*j] += i;
            else
                sum[i*j] += i + j;
        }
    }
    for(int i = 2; i <= 1000000; i++)
        fp[sum[i]-i] = 1;
}
int main()
{
    get();
    int t; Ri(t);
    W(t)
    {
        int n; Ri(n);
        //bool flag = (n==2||n==5);
        printf(fp[n] ? "no
" : "yes
");
    }
    return 0;
}

hdoj 1999 만 질 수 없 는 숫자 [수학 적 인자 와]

좋은 웹페이지 즐겨찾기