CodeForces 300C --数论

时间:2021-10-20 15:21:16
A - A

Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Description

Vitaly is a very weird man. He's got two favorite digits a and b. Vitaly calls a positive integer good, if the decimal representation of this integer only contains digits a and b. Vitaly calls a good number excellent, if the sum of its digits is a good number.

For example, let's say that Vitaly's favourite digits are 1 and 3, then number 12 isn't good and numbers 13 or 311 are. Also, number111 is excellent and number 11 isn't.

Now Vitaly is wondering, how many excellent numbers of length exactly n are there. As this number can be rather large, he asks you to count the remainder after dividing it by 1000000007(109 + 7).

A number's length is the number of digits in its decimal representation without leading zeroes.

Input

The first line contains three integers: abn(1 ≤ a < b ≤ 9, 1 ≤ n ≤ 106).

Output

Print a single integer — the answer to the problem modulo 1000000007(109 + 7).

Sample Input

Input
1 3 3
Output
1
Input
2 3 10
Output
165

这道题的想法很简答,枚举a的个数,判断a*i+b*(n-i)是不是一个good数,如果是的话,那么i个a + n-i个b就可以组成excellent数。
然后求组合数C(i,n)。
问题是C(i,n)很不好求。因为C(i,n)=(n!)/[(i!*(n-i)!],本身数据量就很大,而mod 1e9后,直接计算会造成精度的损失。
这里用到两个知识:费马小定理 乘法逆元,在加一个简单的快速幂。 (1)费马小定理 费马小定理(Fermat Theory)是数论中的一个重要定理,其内容为: 假如p是质数,且Gcd(a,p)=1,那么 a(p-1)(mod p)≡1。即:假如a是整数,p是质数,且a,p互质(即两者只有一个公约数1),那么a的(p-1)次方除以p的余数恒等于1。(我爱度娘(╯‵□′)╯︵┻━┻)。
简而言之就是如果a,p互质,同时p是质数,那么a^(p-1) mod p=1。证明略。 (2)乘法逆元 若对于a,p存在x,使得a*x mod p=1,那么我们称x为a对p的乘法逆元。证明略。
那么乘法逆元存在的意义是什么呢?
假如我们要求(a/b) mod p且无法直接求得a/b的值时,我们可以求出b对p的乘法逆元inv,那么(a/b) mod p=(a*inv) mod p。证明略。。。
bazinga!!!
证明如下:
假如inv是b对于p的乘法逆元,即b*inv=p*t+1(t为整数),移项得inv=(p*t+1)/b
(a*inv) mod p
=(a*((p*t+1)/b)) mod p
=(a*(p*t/b+1/b)) mod p
=(a/b) mod p+(a*(p*t+1)) mod p
=(a/b) mod p+(a*p*t/b) mod p
∵ (a*p*t/b) mod p=0
∴ 原式=(a/b) mod p
即(a*inv) mod p=(a/b) mod p 有了这2个概念我们就可以快速地算出组合数了。
我们可以知道x与x^p-2互为逆元(p是质数)。
/*
证明:x与x^(p-2)互为逆元(p是质数) 由费马小定理:x^(p-1) mod p=1
x*(x^(p-2)) mod p=1
得x与x^(p-2)互为乘法逆元,证毕。
*/
由上述结论可知,要计算C(i,n),即计算n!/(i!*(n-i)!) mod p,那么我们只需要计算n!*(i!*(n-i))^(p-2) mod p。
#include<iostream>
#include<stdio.h>
//#define prim 1000000000+7
using namespace std;
int a,b,n;
const long long prim=1e9+;
long long dp[];
bool exce(long long sum)
{
//cout<<sum<<endl;
while(sum>)
{
if(sum%!=a&&sum%!=b)
return false;
sum/=;
}
return true;
}
long long int comb(long long i)
{
// if(i==0||i==1) return 1;
long long int _i;
_i=dp[i];
long long int _ans=;
long long int p=prim-;
while(p>)
{
if(p&)
_ans=_ans*_i%prim;
_i=_i*_i%prim;
p=p>>; }
return _ans%prim; }
int main()
{
cout<<prim-<<endl;
dp[]=; //printf("%I64d\n%I64d",dp[1000000],dp[1000000-1]);
long long int ans=;
scanf("%d%d%d",&a,&b,&n);
for(long long int i=;i<=n;i++)
{
dp[i]=(dp[i-]*i)%(prim);
}
for(long long int i=;i<=n;i++)
{
if(exce(a*i+b*(n-i)))
{
long long comi=comb(i);
long long comni=comb(n-i);
//cout<<comi<<endl<<comni<<endl;
ans+=dp[n]*comi%prim*comni%prim;
}
}
printf("%I64d\n",ans%prim);
return ;
}
这里我要说明一下,你会发现我的代码里面有两个prim,一个是constant,一个是#define,经过实践检验,我发现用常变量是正确的,用宏是错误的。
虽然我现在还不知道是为什么,但是应该注意到这一点,以后涉及到计算的一律用常变量。
再用宏我就是脑袋有坑。

CodeForces 300C --数论的更多相关文章

  1. CodeForces 300C 最短路

    A Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u Submit Status Pr ...

  2. Codeforces 300C

    题目链接: http://codeforces.com/contest/300/problem/C 本来是道不难的题目,还是自己的数学功底不扎实. 从该题又一次巩固了关于乘法逆的概念,在剩余系中,如果 ...

  3. CodeForces 359D &lpar;数论&plus;二分&plus;ST算法)

    题目链接: http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=47319 题目大意:给定一个序列,要求确定一个子序列,①使得该子序 ...

  4. Codeforces 264B 数论&plus;DP

    题目链接:http://codeforces.com/problemset/problem/264/B 代码: #include<cstdio> #include<iostream& ...

  5. Codeforces Round &num;424 &lpar;Div&period; 2&comma; rated&comma; based on VK Cup Finals&rpar; Problem F &lpar;Codeforces 831F&rpar; - 数论 - 暴力

    题目传送门 传送门I 传送门II 传送门III 题目大意 求一个满足$d\sum_{i = 1}^{n} \left \lceil \frac{a_i}{d} \right \rceil - \sum ...

  6. CodeForces 300C Beautiful Numbers(乘法逆元&sol;费马小定理&plus;组合数公式&plus;高速幂)

    C. Beautiful Numbers time limit per test 2 seconds memory limit per test 256 megabytes input standar ...

  7. CodeForces 1202F&lpar;数论,整除分块&rpar;

    题目 CodeForces 1213G 做法 假设有\(P\)个完整的循环块,假设此时答案为\(K\)(实际答案可能有多种),即每块完整块长度为\(K\),则\(P=\left \lfloor \fr ...

  8. Vasya and Beautiful Arrays CodeForces - 354C &lpar;数论,枚举&rpar;

    Vasya and Beautiful Arrays CodeForces - 354C Vasya's got a birthday coming up and his mom decided to ...

  9. Neko does Maths CodeForces - 1152C 数论欧几里得

    Neko does MathsCodeForces - 1152C 题目大意:给两个正整数a,b,找到一个非负整数k使得,a+k和b+k的最小公倍数最小,如果有多个k使得最小公倍数最小的话,输出最小的 ...

随机推荐

  1. php代码美化&sol;格式化 还原 -问题

    使用某个PHP代码格式化的工具.源代码: if ($this->_standardize_newlines == TRUE) { if (strpos($str, "\r") ...

  2. dede文章页调用当前栏目链接方法

    DedeCMS内容页调用当前栏目其实用下来是调用不出来的,{dede:field.typename/}是有效的,可是 {dede:field.typeurl/}却调不出文档当前栏目所在目录链接URL. ...

  3. display&lowbar;errors &amp&semi; error&lowbar;reporting(php调试安全)

    这两个选项对应的值即都可以在php.ini文件中设置,也都可以在php代码中使用相应的函数来设置. 在php.ini文件中的设置如下:

  4. 用CasperJs自己主动浏览页面

    CasperJs是一个基于PhantomJs的工具,其比起PhantomJs能够更加方便的进行navigation. 一个最简单的CasperJs代码 创建一个文件baidu.js.用来模拟我们訪问百 ...

  5. SpringMVC通过实体类返回json格式的字符串&comma;并在前端显示

    一.除了搭建springmvc框架需要的jar包外,还需要这两个jar包 jackson-core-asl-1.9.2.jar和jackson-mapper-asl-1.9.2.jar 二.web,. ...

  6. Django跨域&lpar;前端跨域&rpar;

    前情回顾 在说今天的问题之前先来回顾一下有关Ajax的相关内容 Ajax的优缺点 AJAX使用Javascript技术向服务器发送异步请求: AJAX无须刷新整个页面: 因为服务器响应内容不再是整个页 ...

  7. castle动态代理的使用

    转自:https://blog.csdn.net/educast/article/details/6565447#动态代理的原理 原理其实很简单,就是在运行时生成新的对象,姑且叫做T,并使T继承自需要 ...

  8. Eclipse代码提示补全问题,自动选择第一个

    原地址 http://blog.csdn.net/liuhhaiffeng/article/details/7179243 Eclipse具有代码提示功能, 但是默认的提示只有在输入".&q ...

  9. python---await&sol;async关键字

    推文:玩转 Python 3.5 的 await/async 首先看正常的两个函数之间的执行 def func1(): print("func1 start") print(&qu ...

  10. FZOJ 2245 动态树(离散&plus;离线&plus; 树状数组)

    Problem 2245 动态树 Accept: 17    Submit: 82Time Limit: 3000 mSec    Memory Limit : 65536 KB  Problem D ...