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

歐拉函數+容斥原理

系統 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條評論
主站蜘蛛池模板: 日产精品久久久一区二区 | 最新国产午夜精品视频不卡 | 全部免费毛片在线 | 伊人情人综合成人久久网小说 | 青草青草久热精品视频99 | 日韩a一级欧美一级在线播放 | 乱人伦精品一区二区 | 国产小视频在线观看www | 国产精品欧美亚洲韩国日本99 | 在线色资源 | 国产在线观看一区二区三区四区 | 手机看片欧美日韩 | 手机看高清特黄a大片 | 婷婷性| 丁香婷婷网 | 国产精品香蕉在线观看不卡 | 曰本性l交视频 | 免费一看一级毛片 | 日本h片a毛片在线播放 | 亚洲综合激情视频 | 91精品国产视频 | 最新av | 国产精品人成福利视频 | 天天透天天插 | 99综合色 | 另类亚洲视频 | 国产高清狼人香蕉在线观看 | 欧美日比视频 | 亚洲天堂国产精品 | 久草在线视频在线观看 | 99爱在线精品视频网站 | 青青青激情视频在线最新 | 亚洲欧美综合图区官网 | 色小妹综合 | 亚洲成色综合一区二区三区四区 | 国产精品免费综合一区视频 | 看片久久 | 天天综合在线观看 | 久久精品综合视频 | 视频精品一区 | 精品91自产拍在线观看一区 |