牛客编程巅峰赛S2第3场 - 钻石&王者ABC

整除问题

https://ac.nowcoder.com/acm/contest/9247/C

ABC题解

A:简单的公式
先看a:显然有a[2]=3*a[1];

a[3] = 3 * a[2]; 显然能找到规律：a[n]=3*a[n-1];

b同理。

然后证明：

a[n] = 2a[n-1] + 3a[n-2];

若a[n-1] = 3*a[n-2] ,则

a[n] = 3*a[n-1]; (带入上式可得)

由于n<=2 时 a[n]=3 * a[n-1];

所以这个关系可以递推到全部。

b同理。

class Solution {
public:
    /**
     * 返回c[n]%1000000007的值
     * @param n long长整型 即题目中的n
     * @return int整型
     */
    long long mod = 1000000007;
    long long qpow(long long a,long long b){
        long long ans=1;
        while(b){
            if(b&1)ans=ans*a%mod;
            a=a*a%mod;
            b/=2;
        }
        return ans;
    }
    int Answerforcn(long long n) {
        // write code here
        n--;
        return qpow(3,n)*2%mod*qpow(5,n)%mod*7%mod;
    }
};

B、Tree VI
由于是完全k叉树，则可以先构造出树，然后dfs遍历它即可。

比赛时我是记录每层的节点数，判断每层是否可以建立节点。

但这样要特判一些东西，其实只要根据完全k叉树的性质，先BFS构造出树，然后dfs遍历算ans即可。(这个代码略。。)

class Solution {
public:
    /**
     * 
     * @param k int整型 表示完全k叉树的叉数k
     * @param a int整型vector 表示这棵完全k叉树的Dfs遍历序列的结点编号
     * @return long长整型
     */
    vector<int>G[100007];
    int dep[100007],cnt=0,b[100007],up=0;
    long long ans=0;
    void dfs(int d,int k,int lst){
        if(dep[d]<=0 || d>up)return ;
        cnt++;
        dep[d]--;
        int now=b[cnt];
        if(cnt>1)ans+=b[cnt]^lst;
        if(d>=up||dep[d+1]<=0)return ;
        for(int i=1;i<=k;i++){
            dfs(d+1,k,now);
        }
    }
     long long tree6(int k, vector<int>& a) {
        // write code here
        for(int i=0;i<a.size();i++)b[i+1]=a[i];
        ans=0;
        if(k==1){
            for(int i=1;i<a.size();i++)ans+=a[i]^a[i-1];
            return ans;
        }
        dep[1]=1;
        int ret=a.size()-1;
        for(int i=2;;i++){
            dep[i]=min(dep[i-1]*k,ret);
            ret-=dep[i];
            if(ret==0){
                up=i;
                break;
            }
        }
        ans=0;
        dfs(1,k,0);
        return ans;
    }
};

C：整除问题
显然有：2021 = 43 * 47

有且仅有 1， 43 ，47， 2021 这4个因子。

若要x*y = k *2021.

x的因子和y因子的并集要同时包含43和47

然后：

分情况：

1：

x包含因子43，y包含因子47.

x包含因子47，y包含因子43.

这种计算会多出：x同时包含43，47因子，y同时包含43，47因子，的情况容斥(即减去这种情况)即可。

2：

x包含因子43，47， y不包含因子43和47(为了不与情况1重复).

x包含因子不包含因子43和47(为了不与情况1重复)，y包含因子43，47.

只有以上2种情况，(相当于把x因子的情况给枚举出来了，只包含43、只包含47、包含2021，只包含1)

typedef long long ll;
class Solution {
public:
    /**
     * 寻找所有能整除 2021 的数对个数
     * @param a long长整型 
     * @param b long长整型 
     * @param c long长整型 
     * @param d long长整型 
     * @return long长整型
     */
    ll cal(ll a,ll b,ll c){
        return b/c - (a-1)/c;
    }
    long long findPairs(long long a, long long b, long long c, long long d) {
        // write code here
        long long ans=0;
        ans+=cal(a,b,43)*cal(c,d,47);
        ans+=cal(a,b,47)*cal(c,d,43);
        ans-=cal(a,b,2021)*cal(c,d,2021);

        ans+=cal(a,b,2021)*(cal(c,d,1)-cal(c,d,47)-cal(c,d,43)+cal(c,d,2021));
        ans+=(cal(a,b,1) - cal(a,b,43) - cal(a,b,47) + +cal(a,b,2021))*cal(c,d,2021);
        return ans;
    }
};