数学问题总结（题目合集）

梦里梦外; 2024-04-17 15:27 87阅读 0赞

## 现在主要攻数据结构。把一些简单的很好的数学问题收集一下，之后再补回来。 ##

## 1、2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018)K. King's Colors ##

## 题意：给出一个含有n个节点的树，以及k个颜色，询问有多少种方式正好用k个颜色给树染色，并且任意两个相邻的节点颜色不同。 ##

## 分析：二项式反演，参考[https://blog.csdn.net/m0\_38081836/article/details/83112463][https_blog.csdn.net_m0_38081836_article_details_83112463]。 ##

## 2、Comet OJ - Contest \#10 C 鱼跃龙门 ##

## 题意： ##

## ![20190907103507137.png][] ##

## 分析： ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70][]

## 代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N=1e6+5;
    int T,l,p[N],pl;
    bool v[N];
    long long x,y,ans,a[N];
    bool fl;
    void ecd(long long a,long long b){
    	if(b==0){
    		if(a!=1){
    			fl=0;return;
    		}
    		fl=1;x=1;y=0;
    		return;
    	}
    	ecd(b,a%b);
    	if(fl){
    		long long t=x;
    		x=y;
    		y=t-a/b*y;
    	}
    }
    long long n;
    int main(){
    	scanf("%d",&T);
    	for(int i=2;i<=1000000;++i){
    		if(!v[i]){
    			p[++pl]=i;
    			for(int o=i+i;o<=1000000;o+=i) v[o]=1;
    		}
    	}
    	for(int i=1;i<=T;++i){
    		scanf("%lld",&n);
    		n<<=1;
    		ans=n;
    		l=0;
    		for(long long i=1;1ll*p[i]*p[i]<=n&&i<=pl;++i){
    			if(n%p[i]==0){
    				a[++l]=p[i];n/=p[i];
    				while(n%p[i]==0){
    					n/=p[i];a[l]*=p[i];
    				}
    			}
    		}
    		if(n!=1){
    			a[++l]=n;
    		}
    		int k=1<<l-1;
    		for(int i=1;i<k;++i){
    			long long X=1,Y=1;
    			for(int o=1,u=1;o<=l;++o,u<<=1){
    				if(u&i) X*=a[o];
    				else Y*=a[o];
    			}
    			ecd(X,Y);
    			if(fl) {
    				ans=min(ans,max(x*X,y*Y));
    			}
    		}
    		printf("%lld\n",ans-1);
    	}
    	return 0;
    }

[https_blog.csdn.net_m0_38081836_article_details_83112463]: https://blog.csdn.net/m0_38081836/article/details/83112463
[20190907103507137.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/af33040abcb14dde90f2c31339e5e667.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3RpYW53ZWkwODIy_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/c6339c20070941438da1bd49d02374be.jpg