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 = 5000000 + 20; 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] = {0, 220, 1184, 2620, 5020, 6232, 10744, 12285, 17296, 63020, 66928, 67095, 69615, 79750, 100485, 122265, 122368,141664, 142310, 171856, 176272, 185368, 196724, 280540, 308620, 319550, 356408, 437456, 469028, 503056, 522405, 600392, 609928, 624184, 635624, 643336, 667964, 726104, 802725, 879712, 898216, 947835, 998104, 1077890, 1154450, 1156870, 1175265, 1185376, 1280565, 1328470, 1358595, 1392368, 1466150, 1468324, 1511930, 1669910, 1798875, 2082464, 2236570, 2652728, 2723792, 2728726, 2739704, 2802416, 2803580, 3276856, 3606850, 3786904, 3805264, 4238984, 4246130, 4259750}; int y[maxn] = {0, 284, 1210, 2924, 5564, 6368, 10856, 14595, 18416, 76084, 66992, 71145, 87633, 88730, 124155, 139815, 123152,153176, 168730, 176336, 180848, 203432, 202444, 365084, 389924, 430402, 399592, 455344, 486178, 514736, 525915, 669688, 686072, 691256, 712216, 652664, 783556, 796696, 863835, 901424, 980984, 1125765, 1043096, 1099390, 1189150, 1292570, 1438983, 1286744, 1340235, 1483850, 1486845, 1464592, 1747930, 1749212, 1598470, 2062570,1870245, 2090656, 2429030, 2941672, 2874064, 3077354, 2928136, 2947216, 3716164, 3721544, 3892670, 4300136, 4006736, 4314616, 4488910, 4445050}; int lena = 71; //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 = 1; i <= lena; ++i) { pre[y[i]] = 1; } for (int i = 1; i <= maxn - 20; ++i) { pre[i] += pre[i - 1]; } } void work() { printf("%d ", pre[n]); } int main() { #ifdef local freopen("data.txt","r",stdin); #endif init(); while (scanf("%d", &n) != EOF) work(); return 0; }