亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

歐拉函數+容斥原理

系統 2084 0

http://acm.hdu.edu.cn/showproblem.php?pid=1695

      
         1
      
      
        /*
      
      
        *


      
      
         2
      
      
             GCD(x,y)=k;在x小于b且y小于d時有多少組答案


      
      
         3
      
      
        2


      
      
         4
      
      
        1 3 1 5 1


      
      
         5
      
      
        1 11014 1 14409 9


      
      
         6
      
      
         7
      
      
        Case 1: 9


      
      
         8
      
      
        Case 2: 736427


      
      
         9
      
      
        10
      
      
        For the first sample input, all the 9 pairs of numbers are 


      
      
        11
      
      
        (1,1),(1,2),(1,3),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5).


      
      
        12
      
      
        *
      
      
        */
      
      
        13
      
       #include <iostream>


      
        14
      
       #include <cstdio>


      
        15
      
       #include <vector>


      
        16
      
       #include <cmath>


      
        17
      
      
        using
      
      
        namespace
      
      
         std;


      
      
        18
      
      
        const
      
      
        int
      
       Ni = 
      
        100010
      
      
        ;


      
      
        19
      
      
        int
      
      
         phi[Ni];


      
      
        20
      
       vector<
      
        int
      
      >
      
         prime[Ni];


      
      
        21
      
      
        long
      
      
        long
      
      
         sphi[Ni];


      
      
        22
      
      
        void
      
       phi_table(
      
        int
      
      
         n)


      
      
        23
      
      
        {


      
      
        24
      
           phi[
      
        1
      
      ]=
      
        1
      
      
        ;


      
      
        25
      
      
        for
      
      (
      
        int
      
       i=
      
        2
      
      ;i<=n;i++) 
      
        if
      
      (!
      
        phi[i])


      
      
        26
      
      
            {


      
      
        27
      
      
        for
      
      (
      
        int
      
       j=i;j<=n;j+=
      
        i)


      
      
        28
      
      
                {


      
      
        29
      
      
        if
      
      (!(phi[j])) phi[j]=
      
        j;


      
      
        30
      
      
                    prime[j].push_back(i);


      
      
        31
      
                   phi[j]-=phi[j]/
      
        i;


      
      
        32
      
      
                }


      
      
        33
      
      
            }


      
      
        34
      
           sphi[
      
        0
      
      ]=
      
        0
      
      
        ;


      
      
        35
      
      
        for
      
      (
      
        int
      
       i=
      
        1
      
      ;i<=n;i++
      
        )


      
      
        36
      
      
            {


      
      
        37
      
               sphi[i]=sphi[i-
      
        1
      
      ]+
      
        phi[i];


      
      
        38
      
      
            }


      
      
        39
      
      
        }


      
      
        40
      
      
        int
      
       dfs(
      
        int
      
       x,
      
        int
      
       b,
      
        int
      
       k) 
      
        ///
      
      
        求0到b中,與k不互質的個數,x為k的第x個質數因子
      
      
        41
      
       {
      
        //
      
      
        容斥定理
      
      
        42
      
      
        int
      
       res=
      
        0
      
      
        ;


      
      
        43
      
      
        for
      
      (
      
        int
      
       i=x;i<prime[k].size();i++
      
        )


      
      
        44
      
               res+=b/prime[k][i]-dfs(i+
      
        1
      
      ,b/
      
        prime[k][i],k);


      
      
        45
      
      
        return
      
      
         res;


      
      
        46
      
      
        }


      
      
        47
      
      
        int
      
      
         main()


      
      
        48
      
      
        {


      
      
        49
      
      
        int
      
      
         t,i;


      
      
        50
      
      
        int
      
       a,b,c,d,k,cs=
      
        1
      
      
        ;


      
      
        51
      
           phi_table(
      
        100005
      
      
        );


      
      
        52
      
           scanf(
      
        "
      
      
        %d
      
      
        "
      
      ,&
      
        t);


      
      
        53
      
      
        for
      
      (cs=
      
        1
      
      ;cs<=t;cs++
      
        )


      
      
        54
      
      
            {


      
      
        55
      
               scanf(
      
        "
      
      
        %d%d%d%d%d
      
      
        "
      
      ,&a,&b,&c,&d,&
      
        k);


      
      
        56
      
      
        if
      
      (k==
      
        0
      
      ) {printf(
      
        "
      
      
        Case %d: 0\n
      
      
        "
      
      ,cs);
      
        continue
      
      
        ;}


      
      
        57
      
      
        58
      
               b/=k;d/=
      
        k;


      
      
        59
      
      
        if
      
      (b>
      
        d) swap(b,d);


      
      
        60
      
      
        long
      
      
        long
      
       ans=
      
        sphi[b];


      
      
        61
      
      
        for
      
      (i=b+
      
        1
      
      ;i<=d;i++
      
        )


      
      
        62
      
      
                {


      
      
        63
      
                   ans+=b-dfs(
      
        0
      
      
        ,b,i);


      
      
        64
      
      
                }


      
      
        65
      
               printf(
      
        "
      
      
        Case %d: %I64d\n
      
      
        "
      
      
        ,cs,ans);


      
      
        66
      
      
            }


      
      
        67
      
      
        return
      
      
        0
      
      
        ;


      
      
        68
      
       }
    

?

歐拉函數+容斥原理


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 日本一级高清片免费 | 成人综合网址 | 97dyy在线观看手机版 | 欧美毛片性视频区 | 天天操天天干天天玩 | 久久久久9| 天天操夜夜骑 | 国产精品永久免费自在线观看 | 亚洲精品久久婷婷爱久久婷婷 | 久久精品国产99国产精品澳门 | 黄色片网站大全 | 四虎国产精品视频免费看 | 国产精品18久久久久久久久久 | 欧美日韩中文国产一区二区三区 | 成人在线观看不卡 | 精品无码久久久久久久动漫 | 久久精品免视看国产成人2021 | 热综合一本伊人久久精品 | 久久噜噜久久久精品66 | 亚洲精品福利视频 | 亚洲天堂一区在线 | 国产一区二区三区四 | 2019年国产高清情侣视频 | 国产在线乱子伦一区二区 | 91最新视频在线观看 | 欧美日韩中文字幕在线视频 | 日操夜操 | 香蕉福利久久福利久久香蕉 | 久久久伊人影院 | 国产成人在线视频播放 | 四虎精品免费国产成人 | 男女交黄| 亚洲另类视频在线观看 | 国产精品一区二区三区久久 | 中文字幕在线观看一区二区三区 | 免费一级a毛片在线播出 | 一区二区中文字幕在线观看 | 黄色免费毛片 | 天天草人人草 | 亚洲精品久久久久久下一站 | 香蕉狠狠干 |