二分判定就是要求小于等于n的合法的数的个数

不难发现一个数若为完全平方数的倍数 则他的质因子肯定有一个的指数大于1

那么合法的数的所有质因数质数肯定都为1

于是题目变为 求小于等于的质因数指数都为1的数的个数

我们可以把<=n的 所有i^2的倍数的数减掉(i为质数)

算重？

莫比乌斯函数！（容斥原理- -）

答案就是n-奇数个质数的平方的倍数的个数+偶数个质数的平方的倍数的个数

即 ans=Σmiu[i]*(n/i^2) （i<=(int) sqrt(n) 显然i如果>sqrt(n)个数肯定为0）

1 (i为奇数个质数的乘积)

miu[i]= -1 (i为偶数个质数的乘积)

0 (i有某个质数指数>1)

P1889天真的因数分解Accepted
记录信息
评测状态 Accepted
题目 P1889 天真的因数分解
递交时间 2016-02-06 15:05:02
代码语言 C++
评测机 ShadowShore
消耗时间 730 ms
消耗内存 8876 KiB
评测时间 2016-02-06 15:05:05
评测结果
编译成功

测试数据 #0: Accepted, time = 15 ms, mem = 8876 KiB, score = 10
测试数据 #1: Accepted, time = 15 ms, mem = 8872 KiB, score = 10
测试数据 #2: Accepted, time = 31 ms, mem = 8872 KiB, score = 10
测试数据 #3: Accepted, time = 62 ms, mem = 8872 KiB, score = 10
测试数据 #4: Accepted, time = 78 ms, mem = 8876 KiB, score = 10
测试数据 #5: Accepted, time = 109 ms, mem = 8876 KiB, score = 10
测试数据 #6: Accepted, time = 93 ms, mem = 8876 KiB, score = 10
测试数据 #7: Accepted, time = 109 ms, mem = 8872 KiB, score = 10
测试数据 #8: Accepted, time = 109 ms, mem = 8872 KiB, score = 10
测试数据 #9: Accepted, time = 109 ms, mem = 8872 KiB, score = 10
Accepted, time = 730 ms, mem = 8876 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
#define MAXN 500000

using namespace std;

bool flag[ MAXN + 2 ];
long long prime[ MAXN + 2 ] , mu[ MAXN + 2 ] , cnt;
long long t , k , l , r , mid , ans;

inline void shake()
{
mu[1] = 1;
for( register long long i = 2 ; i <= MAXN ; i++ )
{
if( !flag[i] )
{
prime[ ++cnt ] = i;
mu[i] = -1;
}
for( register long long j = 1 ; j <= cnt ; j++ )
{
if( ( long long ) i * prime[j] > MAXN ) break;
flag[ i * prime[j] ] = 1;
mu[ i * prime[j] ] = -mu[i];
if( i % prime[j] == 0 )
{
mu[ i * prime[j] ] = 0;
break;
}
}
}
}

inline long long sum( register long long x )
{
register long long sum = 0;
for( register long long i = 1 ; i * i <= x ; i++ )
sum += x / ( i * i ) * mu[i];
return x - sum;
}

inline bool check( long long x )
{
long long s = sum( x );
return s >= k;
}

int main()
{
shake();
cin >> k;
l = 0 , r = k << 3;
while( l <= r )
{
mid = ( l + r ) >> 1;
if( check( mid ) ) r = mid - 1 , ans = mid;
else l = mid + 1;
}
cout << ans << endl;
return 0;
}

莫比乌斯函数

很容易想到因式分解之后瞎搞。。但是我用rho+miller-rabin搞了很久还是只有89分>_<。。 看了标程之后才明白，因为所有数小于10^18，那么首先用所有小于10^6的素数去除。。 那么接下来的数如果有3个质因数pqr，就矛盾了。所以只可能是p，pq,p^2这样的形式。。 然后考虑它们之间两两的最大公约数。由于所有数最多只有2个素因子，那么如果该最大公约数是某数的真因子。就肯定是素数。。 
然后考虑某数可能是p^2的情况。。根号一下就可以了。。 
然后剩下来的数要么是pq,要么是p。。而且两两之间要么相等要么互质。。所以可以直接拿pq去除所有数。。结果算两份就可以了。。 然后用miller-rabin判断是否是素数。。OK了

    var
        pri,u : array[1..200000] of longint;
        mark : array[1..200000] of boolean;
        tot : longint;
        l,r,mid,k : int64;
    
    procedure init;
    var
        i,j : longint;
    begin
        for i := 2 to 200000 do
        begin
            if not mark[i] then
            begin
                u[i] := 1; inc(tot); pri[tot] := i;
            end;
            for j := 1 to tot do
            begin
                if pri[j]*i > 200000 then break;
                mark[pri[j]*i] := true; u[i*pri[j]] := -u[i];
                if i mod pri[j] = 0 then begin u[i*pri[j]] := 0; break; end;
            end;
        end;
    end;
    
    function get(n:int64):int64;
    var
        i : longint;
    begin
        get := 0;
        for i := 2 to trunc(sqrt(n)) do inc(get,u[i]*(n div sqr(int64(i))));
    end;
    
    begin
        readln(k);
        init;
        l := 1; r :=  1 << 36;
        while l < r do
        begin
            mid := (l+r) >> 1;
            if get(mid) < k then l := mid+1 else r := mid;
        end;
        writeln(l);
    end.
    

利用莫比乌斯函数是积性函数的性质。。。
线性解决。。。

BZOJ2440.

mobius反演。。
这真的是一套noip题吗。。。

hehe

..

4,8,9,12,16,18,20,24,25,27,28,32,36,40,44,45,48,49,50,52,54,56,60,63,64,68,72,75,76,80,81,84,88,90,92,96,98,99,100,104,108,112,116,117,120,121,124,125,126,128,132,135,136,140,144,147,148,150,152,153,156,160,162,164,168,169,171,172,175,176,180,184,188,189,192,196,198,200,204,207,208,212,216,220,224,225,228,232,234,236,240,242,243,244,245,248,250,252,256,260,261,264,268,270,272,275,276,279,280,284,288,289,292,294,296,297,300,304,306,308,312,315,316,320,324,325,328,332,333,336,338,340,342,343,344,348,350,351,352,356,360,361,363,364,368,369,372,375,376,378,380,384,387,388,392,396,400,404,405,408,412,414,416,420,423,424,425,428,432,436,440,441,444,448,450,452,456,459,460,464,468,472,475,476,477,480,484,486,488,490,492,495,496,500,504,507,508,512,513,516,520,522,524,525,528,529,531,532,536,539,540,544,548,549,550,552,556,558,560,564,567,568,572,575,576,578,580,584,585,588,592,594,596,600,603,604,605,608,612,616,620,621,624,625,628,630,632,636,637,639,640,644,648,650,652,656,657,660,664,666,668,672,675,676,680,684,686,688,692,693,696,700,702,704,708,711,712,716,720,722,724,725,726,728,729,732,735,736,738,740,744,747,748,750,752,756,760,764,765,768,772,774,775,776,780,783,784,788,792,796,800,801,804,808,810,812,816,819,820,824,825,828,832,833,836,837,840,841,844,845,846,847,848,850,852,855,856,860,864,867,868,872,873,875,876,880,882,884,888,891,892,896,900,904,908,909,912,916,918,920,924,925,927,928,931,932,936,940,944,945,948,950,952,954,956,960,961,963,964,968,972,975,976,980,981,984,988,990,992,996,999,1000,1004,1008,1012,1014,1016,1017,1020,1024,1025,1026,1028,1029,1032,1035,1036,1040,1044,1048,1050,1052,1053,1056,1058,1060,1062,1064,1068,1071,1072,1075,1076,1078,1080,1083,1084,1088,1089,1092,1096,1098,1100,1104,1107,1108,1112,1116,1120,1124,1125,1127,1128,1132,1134,1136,1140,1143,1144,1148,1150,1152,1156,1160,1161,1164,1168,1170,1172,1175,1176,1179,1180,1183,1184,1188,1192,1196,1197,1200,1204,1206,1208,1210,1212,1215,1216,1220,1224,1225,1228,1232,1233,1236,1240,1242,1244,1248,1250,1251,1252,1256,1260,1264,1268,1269,1272,1274,1275,1276,1278,1280,1284,1287,1288,1292,1296,1300,1304,1305,1308,1312,1314,1316,1320,1323,1324,1325,1328,1331,1332,1336,1340,1341,1344,1348,1350,1352,1356,1359,1360,1364,1368,1369,1372,1375,1376,1377,1380,1384,1386,1388,1392,1395,1396,1400,1404,1408,1412,1413,1416,1420,1421,1422,1424,1425,1428,1431,1432,1436,1440,1444,1445,1448,1449,1450,1452,1456,1458,1460,1464,1467,1468,1470,1472,1475,1476,1480,1484,1485,1488,1492,1494,1496,1500,1503,1504,1508,1512,1516,1519,1520,1521,1524,1525,1528,1530,1532,1536,1539,1540,1544,1548,1550,1552,1556,1557,1560,1564,1566,1568,1572,1573,1575,1576,1580,1584,1587,1588,1592,1593,1596,1600,1602,1604,1608,1611,1612,1616,1617,1620,1624,1625,1628,1629,1632,1636,1638,1640,1644,1647,1648,1650,1652,1656,1660,1664,1665,1666,1668,1672,1674,1675,1676,1680,1681,1682,1683,1684,1688,1690,1692,1694,1696,1700,1701,1704,1708,1710,1712,1715,1716,1719,1720,1724,1725,1728,1732,1734,1736,1737,1740,1744,1746,1748,1750,1752,1755,1756,1760,1764,1768,1772,1773,1775,1776,1780,1782,1784,1788,1791,1792,1796,1800,1804,1805,1808,1809,1812,1813,1815,1816,1818,1820,1824,1825,1827,1828,1832,1836,1840,1844,1845,1848,1849,1850,1852,1854,1856,1859,1860,1862,1863,1864,1868,1872,1875,1876,1880,1881,1884,1888,1890,1892,1896,1899,1900,1904,1908,1911,1912,1916,1917,1920,1922,1924,1925,1926,1928,1932,1935,1936,1940,1944,1948,1950,1952,1953,1956,1960,1962,1964,1968,1971,1972,1975,1976,1980,1984,1988,1989,1992,1996,1998,2000,2004,2007,2008,2009,2012,2016,2020,2023,2024,2025,2028,2032,2034,2036,2040,2043,2044,2048,2050,2052,2056,2057,2058,2060,2061,2064,2068,2070,2072,2075,2076,2079,2080,2084,2088,2092,2096,2097,2100,2104,2106,2107,2108,2112,2115,2116,2120,2124,2125,2128,2132,2133,2136,2140,2142,2144,2148,2150,2151,2152,2156,2160,2164,2166,2168,2169,2172,2175,2176,2178,2180,2184,2187,2188,2192,2196,2197,2200,2204,2205,2208,2209,2212,2214,2216,2220,2223,2224,2225,2228,2232,2236,2240,2241,2244,2248,2250,2252,2254,2256,2259,2260,2264,2268,2272,2275,2276,2277,2280,2284,2286,2288,2292,2295,2296,2299,2300,2303,2304,2308,2312,2313,2316,2320,2322,2324,2325,2328,2331,2332,2336,2340,2344,2348,2349,2350,2352,2356,2358,2360,2364,2366,2367,2368,2372,2375,2376,2380,2384,2385,2388,2392,2394,2396,2400,2401,2403,2404,2408,2412,2416,2420,2421,2424,2425,2428,2430,2432,2436,2439,2440,2444,2448,2450,2452,2456,2457,2460,2464,2466,2468,2472,2475,2476,2480,2484,2488,2492,2493,2496,2499,2500,2502,2504,2508,2511,2512,2516,2520,2523,2524,2525,2527,2528,2529,2532,2535,2536,2538,2540,2541,2544,2547,2548,2550,2552,2556,2560,2564,2565,2568,2572,2574,2575,2576,2580,2583,2584,2588,2592,2596,2597,2600,2601,2604,2608,2610,2612,2616,2619,2620,2624,2625,2628,2632,2636,2637,2640,2644,2645,2646,2648,2650,2652,2655,2656,2660,2662,2664,2668,2672,2673,2675,2676,2680,2682,2684,2688,2691,2692,2695,2696,2700,2704,2708,2709,2712,2716,2718,2720,2724,2725,2727,2728,2732,2736,2738,2740,2744,2745,2748,2750,2752,2754,2756,2760,2763,2764,2768,2772,2775,2776,2780,2781,2783,2784,2788,2790,2792,2793,2796,2799,2800,2804,2808,2809,2812,2816,2817,2820,2824,2825,2826,2828,2832,2835,2836,2840,2842,2844,2848,2850,2852,2853,2856,2860,2862,2864,2868,2871,2872,2873,2875,2876,2880,2883,2884,2888,2889,2890,2891,2892,2896,2898,2900,2904,2907,2908,2912,2916,2920,2924,2925,2928,2932,2934,2936,2940,2943,2944,2948,2950,2952,2956,2960,2961,2964,2968,2970,2972,2975,2976,2979,2980,2984,2988,2989,2992,2996,2997,3000,3004,3006,3008,3012,3015,3016,3020,3024,3025,3028,3032,3033,3036,3038,3040,3042,3044,3048,3050,3051,3052,3056,3060,3064,3068,3069,3072,3075,3076,3078,3080,3084,3087,3088,3092,3096,3100,3104,3105,3108,3112,3114,3116,3120,3123,3124,3125,3128,3132,3136,3140,3141,3144,3146,3148,3150,3152,3156,3159,3160,3164,3168,3172,3174,3175,3176,3177,3179,3180,3184,3185,3186,3188,3192,3195,3196,3200,3204,3208,3211,3212,3213,3216,3220,3222,3224,3225,3228,3231,3232,3234,3236,3240,3244,3248,3249,3250,3252,3256,3258,3260,3264,3267,3268,3272,3275,3276,3280,3283,3284,3285,3288,3292,3294,3296,3300,3303,3304,3308,3312,3316,3320,3321,3324,3325,3328,3330,3332,3336,3339,3340,3344,3348,3350,3352,3356,3357,3360,3362,3364,3366,3368,3372,3375,3376,3380,3381,3384,3388,3392,3393,3396,3400,3402,3404,3408,3411,3412,3416,3420,3424,3425,3428,3429,3430,3432,3436,3438,3440,3444,3447,3448,3450,3452,3456,3460,3464,3465,3468,3472,3474,3475,3476,3479,3480,3481,3483,3484,3488,3492,3496,3500,3501,3504,3508,3509,3510,3512,3516,3519,3520,3524,3525,3528,3532,3536,3537,3540,3544,3546,3548,3549,3550,3552,3555,3556,3560,3564,3568,3572,3573,3575,3576,3577,3580,3582,3584,3588,3591,3592,3596,3600,3604,3608,3609,3610,3612,3616,3618,3620,3624,3625,3626,3627,3628,3630,3632,3636,3640,3644,3645,3648,3650,3652,3654,3656,3660,3663,3664,3668,3672,3675,3676,3680,3681,3684,3688,3690,3692,3696,3698,3699,3700,3703,3704,3708,3712,3716,3717,3718,3720,3721,3724,3725,3726,3728,3732,3735,3736,3740,3744,3748,3750,3751,3752,3753,3756,3757,3760,3762,3764,3768,3771,3772,3773,3775,3776,3780,3784,3788,3789,3792,3796,3798,3800,3804,3807,3808,3812,3816,3820,3822,3824,3825,3828,3832,3834,3836,3840,3843,3844,3848,3850,3852,3856,3860,3861,3864,3868,3870,3871,3872,3875,3876,3879,3880,3884,3887,3888,3892,3896,3897,3900,3904,3906,3908,3912,3915,3916,3920,3924,3925,3928,3932,3933,3936,3940,3942,3944,3948,3950,3951,3952,3956,3960,3964,3968,3969,3971,3972,3975,3976,3978,3980,3984,3987,3988,3992,3993,3996,4000,4004,4005,4008,4012,4014,4016,4018,4020,4023,4024,4025,4028,4032,4036,4040,4041,4044,4046,4048,4050,4052,4056,4059,4060,4064,4067,4068,4072,4075,4076,4077,4080,4084,4086,4088,4092,4095,4096,4100,4104,4107,4108,4112,4113,4114,4116,4120,4122,4124,4125,4128,4131,4132,4136,4140,4144,4148,4149,4150,4152,4156,4158,4160,4164,4165,4167,4168,4172,4175,4176,4180,4184,4185,4188,4192,4194,4196,4200,4203,4204,4205,4208,4212,4214,4216,4220,4221,4224,4225,4228,4230,4232,4235,4236,4239,4240,4244,4248,4250,4252,4256,4257,4260,4263,4264,4266,4268,4272,4275,4276,4280,4284,4288,4292,4293,4296,4300,4302,4304,4308,4311,4312,4316,4320,4324,4325,4328,4329,4332,4335,4336,4338,4340,4344,4347,4348,4350,4352,4356,4360,4361,4364,4365,4368,4372,4374,4375,4376,4380,4383,4384,4388,4392,4394,4396,4400,4401,4404,4408,4410,4412,4416,4418,4419,4420,4424,4425,4428,4432,4436,4437,4440,4444,4446,4448,4450,4452,4455,4456,4459,4460,4464,4468,4472,4473,4475,4476,4477,4480,4482,4484,4488,4489,4491,4492,4496,4500,4504,4508,4509,4512,4516,4518,4520,4524,4525,4527,4528,4532,4536,4540,4544,4545,4548,4550,4552,4554,4556,4557,4560,4563,4564,4568,4572,4575,4576,4580,4581,4584,4588,4590,4592,4596,4598,4599,4600,4604,4606,4608,4612,4616,4617,4620,4624,4625,4626,4628,4632,4635,4636,4640,4644,4648,4650,4652,4653,4655,4656,4660,4662