d044 - 00640 - Self Numbers
題目描述
題目要求找出所有小於等於 1000000 的 self numbers。Self number 定義為沒有 generator 的數字。Generator 的定義是，如果 n 是 d(n) 的 generator，則 d(n) = n + n 的各位數字和。
解題思路
程式碼使用一個布林陣列 ans 來標記哪些數字有 generator。對於每個數字 i 從 0 到 999999，計算 d(i)，並將 ans[d(i)] 設為 1，表示 d(i) 有 i 作為 generator。最後，遍歷 ans 陣列，輸出所有 ans[i] 為 0 的數字 i，這些數字就是 self numbers。
複雜度分析
- 時間複雜度: O(N * logN)，其中 N 是 1000000。計算 d(i) 的時間複雜度是 O(logN)，因為需要遍歷 i 的每一位數字。
- 空間複雜度: O(N)，因為需要一個大小為 1000001 的布林陣列
ans。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
char ans[1100001];
inline void write(int x) {
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
for(int i=0;i<1000000;++i){
int a=i,b=i;
while(a){
b+=a%10;
a/=10;
}
ans[b]=1;
}
for(int i=0;i<=1000000;++i)
if(ans[i]==0){
write(i);
putchar_unlocked('\n');
}
}