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

歐拉函數+容斥原理

系統 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條評論
主站蜘蛛池模板: 日本免费人成黄页网观看视频 | 一级做性色a爱片久久片 | 在线精品国内视频秒播 | 成年人免费在线视频 | 久久免费高清视频 | 人做人爱视频欧美在线观看 | 欧美一级片网 | 视频在线亚洲 | 天天干天天射天天插 | 久99久爱精品免费观看视频 | 亚洲国产品综合人成综合网站 | julia在线播放 | 精品动漫一区二区三区 | 国产精品 视频一区 二区三区 | 欧美精品免费在线观看 | 在线亚洲欧美性天天影院 | 成人欧美一区二区三区 | 久久久久久尹人网香蕉 | 日产精品一区二区 | 欧美精品视 | 一本一本久久α久久精品66 | 久久精品免费一区二区视 | 亚洲欧美日韩在线不卡中文 | 奇米777影视成人四色 | 伊色综合久久之综合久久 | 亚洲国产字幕 | 一级毛片视频 | 精品综合久久久久久88小说 | 91手机在线视频观看 | 久久婷婷国产一区二区三区 | 欧美性猛交99久久久久99 | 色97色| 最新中文字幕一区二区乱码 | 欧美日韩一区在线观看 | 亚洲综合专区 | 精品久久中文字幕 | 亚洲系列中文字幕一区二区 | 久久免费在线视频 | 狠狠亚洲丁香综合久久 | 国产91久久久久久久免费 | 91久久亚洲国产成人精品性色 |