秒懂算法 | 数论算法实例分析之阿里巴巴的宝藏与欧拉函数例题

数学( math )在计算机科学中的应用非常广泛,是程序设计的一门辅助学科,有人这样说过:“一切计算机问题终归于数学问题!”,而数论是一个非常庞大的数学分支,对于程序设计来说很重要,但它不是程序设计的全部,本章将讨论几类数论问题,并用程序实现它们。

01、实例分析：阿里巴巴的宝藏

问题描述:

阿里巴巴和马尔吉娜来到一条布满黄金的街道。他们想带几块黄金回去，然而这里的城管担心他们拿得太多，于是要求阿里巴巴和马尔吉娜通过做一个游戏决定最后得到的黄金数量。

游戏规则是这样的:

假设道路长度为n米(左端点为0，右端点为n)，同时给出一个数k(下面会提到k的用法)。

设阿里巴巴初始时的黄金数量为A，马尔吉娜初始时的黄金数量为B。阿里巴巴从1出发走向n-1，马尔吉娜从n-1出发走向1，两人的速度均为1m/s。

假设某一时刻(必须为整数)阿里巴巴的位置为x，马尔吉娜的位置为y，若gcd(n,x)=1且gcd(n,y)=1，那么阿里巴巴的黄金数量A会变为A*kxkg，马尔吉娜的黄金数量B会变为B*kykg。当阿里巴巴到达n-1时，游戏结束。

阿里巴巴想知道游戏结束时A+B的值。

答案为对109+7取模。

输入描述:

一行四个整数n,k,A,B。

输出描述:

输出一个整数，表示答案。

样例: