nyoj-Color the necklace(Ploya定理 + 欧拉函数 + 扩展欧几里得(求逆元))

本文主要是介绍nyoj-Color the necklace(Ploya定理 + 欧拉函数 + 扩展欧几里得(求逆元)),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:http://acm.nyist.net/JudgeOnline/problem.php?pid=688

此题题解 不太懂,因为对这些概念,定理太模糊,理解起来比较困难,不过想想还是应该把代码写出来;


题意:给你一个数 n ,代表 n 种颜色和n个珠子,问你可以组合多少种长度为n的项链;不需要用掉n种颜色,项链的旋转和翻转都是为同一条

题解: http://pan.baidu.com/s/1ntwPVkd#dir/path=%2FACM%E5%A5%97%E9%A2%98%2F09%E5%B9%B4%20-%203rd%20Central%20South%20China%20Programming%20Contest%2Fcsc2009%2FC%2Fsolution

点进去之后点击C.ppt


公式:


#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL mod = 20090531;
LL x,y;
LL euler(LL p)//欧拉定理
{LL res = p;for(LL i = 2;i <= sqrt(p);i++){if(p%i==0){while(p%i==0) p/=i;res = res/i*(i-1);}}if(p > 1) res = res / p * (p-1);return res%mod;
}
LL fast_pow(LL a,LL b)//快速幂
{LL res = 1;while(b){if(b&1) res = (res * a) % mod;a = (a * a) % mod;b >>= 1;}return res;
}
void edgcd(LL a,LL b)//求逆元
{if(b == 0){x = 1;y = 0;return;}edgcd(b,a%b);LL temp = x;x = y;y = temp - a/b*y;
}
void solve(LL m)
{LL res = 0;for(LL i = 1;i <= sqrt(m);i++){if(m%i==0){if(m/i != i) res = (res + euler(i)*fast_pow(m,m/i-1))%mod;res = (res + euler(m/i)*fast_pow(m,i-1))%mod;}}if(m&1){res = (fast_pow(m,(m+1)/2) + res) % mod;edgcd(2,mod);}else{res = (fast_pow(m,m/2+1) + fast_pow(m,m/2) + 2 * res) % mod;edgcd(4,mod);}while(x < 0) x = (x + mod) % mod;printf("%lld\n",x * res % mod);
}
int main()
{int n;LL m;scanf("%d",&n);while(n--){scanf("%lld",&m);solve(m);}
}


这篇关于nyoj-Color the necklace(Ploya定理 + 欧拉函数 + 扩展欧几里得(求逆元))的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1009317

相关文章

Android Kotlin 高阶函数详解及其在协程中的应用小结

《AndroidKotlin高阶函数详解及其在协程中的应用小结》高阶函数是Kotlin中的一个重要特性,它能够将函数作为一等公民(First-ClassCitizen),使得代码更加简洁、灵活和可... 目录1. 引言2. 什么是高阶函数?3. 高阶函数的基础用法3.1 传递函数作为参数3.2 Lambda

Java常用注解扩展对比举例详解

《Java常用注解扩展对比举例详解》:本文主要介绍Java常用注解扩展对比的相关资料,提供了丰富的代码示例,并总结了最佳实践建议,帮助开发者更好地理解和应用这些注解,需要的朋友可以参考下... 目录一、@Controller 与 @RestController 对比二、使用 @Data 与 不使用 @Dat

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

kotlin的函数forEach示例详解

《kotlin的函数forEach示例详解》在Kotlin中,forEach是一个高阶函数,用于遍历集合中的每个元素并对其执行指定的操作,它的核心特点是简洁、函数式,适用于需要遍历集合且无需返回值的场... 目录一、基本用法1️⃣ 遍历集合2️⃣ 遍历数组3️⃣ 遍历 Map二、与 for 循环的区别三、高

Spring组件初始化扩展点BeanPostProcessor的作用详解

《Spring组件初始化扩展点BeanPostProcessor的作用详解》本文通过实战案例和常见应用场景详细介绍了BeanPostProcessor的使用,并强调了其在Spring扩展中的重要性,感... 目录一、概述二、BeanPostProcessor的作用三、核心方法解析1、postProcessB

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

MySQL中COALESCE函数示例详解

《MySQL中COALESCE函数示例详解》COALESCE是一个功能强大且常用的SQL函数,主要用来处理NULL值和实现灵活的值选择策略,能够使查询逻辑更清晰、简洁,:本文主要介绍MySQL中C... 目录语法示例1. 替换 NULL 值2. 用于字段默认值3. 多列优先级4. 结合聚合函数注意事项总结C

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

MySQL 日期时间格式化函数 DATE_FORMAT() 的使用示例详解

《MySQL日期时间格式化函数DATE_FORMAT()的使用示例详解》`DATE_FORMAT()`是MySQL中用于格式化日期时间的函数,本文详细介绍了其语法、格式化字符串的含义以及常见日期... 目录一、DATE_FORMAT()语法二、格式化字符串详解三、常见日期时间格式组合四、业务场景五、总结一、