17115 ooxx numbers
时间限制:1000MS 内存限制:65535K
提交次数:0 通过次数:0
题型: 编程题 语言: G++;GCC
Description
a number A called oo number of a number B if the sum of all As factor is the number B.
(A,B) is a pair of ooxx numbers if A is the oo number of B and B is the oo number of A.
Now i want to find how many pairs of ooxx numbers in [1,n]
输入格式
there are many cases in the input.
for each line there is a number n. ( 1 <= n <= 5000000 )
输出格式
for each n, output the numbers of pairs of ooxx numbers in [1,n]
输入样例
300
1300
输出样例
1
2
提示
hits
220=1+2+4+71+142=284,
284=1+2+4+5+10+11+20+22+44+55+110=220。
220 and 280 is a pair of ooxx numbers.
作者
admin
明显可以用nlogn完成book[i]表示i这个数的所有因子和，然后打表。但是题目还是卡了nlogn。所以就交表。
用pair x y表示他们是同一对生成元，然后保证x是小于y的，（这个在打表的时候可以确保，从小到大枚举，如果有的话，就会先进入了）
然后对y进行前缀和，因为y是大于x的，所以y才是有意义的。就是220和280，问250是没有的，问280才行。
pre[i]表示小于等于i的数字中有多少个答案。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
LL book[maxn];
struct node {
int x, y;
bool operator < (const struct node & rhs) const {
if (x != rhs.x) {
return x < rhs.x;
} else return y < rhs.y;
}
}a[maxn];
int x[maxn] = {, , , , , , , , , , , , , , , , ,, , , , , , , , , , , , , , , ,
, , , , , , , , , , ,
, , , , , , , , , , , , , , , , , , , , , , , , , , , }; int y[maxn] = {, , , , , , , , , , , , , , , , ,, , , , , , , , , , , , , , , , , , , , , , , , , , ,
, , , , , , , , , , , ,, , , , , , , , , , , , , , , };
int lena = ;
//bool vis[maxn];
//void init() {
// for (int i = 1; i <= maxn - 20; ++i) {
// for (int j = 2 * i; j <= maxn - 20; j += i) {
// book[j] += i;
// }
// }
// lena = 0;
// for (int i = 1; i <= maxn - 20; ++i) {
// if (book[i] <= maxn - 20) {
// if (!vis[i] && book[book[i]] == i && book[i] != i) {
// ++lena;
// a[lena].x = i;
// a[lena].y = book[i];
// vis[i] = true;
// vis[book[i]] = true;
// }
// }
// }
// sort(a + 1, a + 1 + lena);
// for (int i = 1; i <= maxn - 20; ++i) {
// x[i] = a[i].x;
// y[i] = a[i].y;
// }
// for (int i = 1; i <= 10; ++i) {
// cout << a[i].x << " " << a[i].y << endl;
// }
//}
int n;
int pre[maxn];
void init() {
for (int i = ; i <= lena; ++i) {
pre[y[i]] = ;
}
for (int i = ; i <= maxn - ; ++i) {
pre[i] += pre[i - ];
}
}
void work() {
printf("%d\n", pre[n]);
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
init();
while (scanf("%d", &n) != EOF) work();
return ;
}